本文涉及知识点

C++动态规划

LeetCode2370. 最长理想子序列

给你一个由小写字母组成的字符串 s ，和一个整数 k 。如果满足下述条件，则可以将字符串 t 视作是 理想字符串 ：
t 是字符串 s 的一个子序列。
t 中每两个 相邻 字母在字母表中位次的绝对差值小于或等于 k 。
返回 最长 理想字符串的长度。
字符串的子序列同样是一个字符串，并且子序列还满足：可以经由其他字符串删除某些字符（也可以不删除）但不改变剩余字符的顺序得到。
注意：字母表顺序不会循环。例如，‘a’ 和 ‘z’ 在字母表中位次的绝对差值是 25 ，而不是 1 。
示例 1：
输入：s = “acfgbd”, k = 2
输出：4
解释：最长理想字符串是 “acbd” 。该字符串长度为 4 ，所以返回 4 。
注意 “acfgbd” 不是理想字符串，因为 ‘c’ 和 ‘f’ 的字母表位次差值为 3 。
示例 2：
输入：s = “abcd”, k = 3
输出：4
解释：最长理想字符串是 “abcd” ，该字符串长度为 4 ，所以返回 4 。
提示：
1 <= s.length <= 10⁵
0 <= k <= 25
s 由小写英文字母组成

动态规划

动态规划的状态表示

dp[i][j]表示s的前i个字符的以’a’+j结尾子序列的最大长度。空间复杂度：O(n$\sum$)

动态规划的填表顺序

枚举前置状态，i = 0 to n-1。

动态规划的转移方程

dp[i+1] = dp[i] 不选择s[i]
if( abs(s[i]-‘a’-j) <= k ) maxSelf(dp[i+1][s[i]-‘a’],dp[i][j]+1)
单个状态转移的时间复杂度**：O(1) 时间复杂度：O(n$\sum$)

动态规划的初始值

全为0。

动态规划的返回值

max(dp.back())

代码

核心代码

		class Solution {
		public:
			int longestIdealString(string s, int k) {
				const int N = s.length();
				vector<vector<int>> dp(N + 1, vector<int>(26));
				for (int i = 0; i < N; i++) {
					dp[i + 1] = dp[i];
					for (int j = 0; j < 26; j++) {
						const int j1 = s[i] - 'a';
						if (abs(j1 - j) <= k) {
							dp[i + 1][j1] = max(dp[i + 1][j1], dp[i][j] + 1);
						}
					}
				}
				return *max_element(dp.back().begin(), dp.back().end());
			}
		};

单元测试

string s;
		int k;
		TEST_METHOD(TestMethod11)
		{
			s = "acfgbd", k = 2;
			auto res = Solution().longestIdealString(s, k);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod12)
		{
			s = "abcd", k = 3;
			auto res = Solution().longestIdealString(s, k);
			AssertEx(4, res);
		}