文章目录
- Day55_动态规划
- 47. 判断子序列
- 48. 不同的子序列
Day55_动态规划
47. 判断子序列
392. 判断子序列
思路:
双指针很简单,O(n)O(n)O(n) 时间就能解决
这里还是用dp
dp[i][j]
表示以s[i - 1]
结尾的字符串和以t[]i-1
为结尾的字符串的最大子序列长度- 地推公式
- 如果匹配上了,即
s[i - 1] == t[j - 1]
,则从上一次的子序列长度加1,dp[i][j] = dp[i - 1][j - 1] + 1;
- 没匹配上,则
dp[i][j] = dp[i][j - 1];
则保留上次的子序列长度,继续向后匹配 t
- 初始化,如图,初始化来自左上角和左边,初始化
dp[0][0]
和dp[i][0]
为 0
- 遍历顺序:遍历顺序是从左上到右下,外层是 s 内层是 t
class Solution {
public:bool isSubsequence(string s, string t) {int s_len = s.length();int t_len = t.length();vector<vector<int>> dp(s_len + 1, vector<int>(t_len + 1, 0));for (int i = 1; i <= s_len; i++) {for (int j = 1; j <= t_len; j++) {if (s[i - 1] == t[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1; // 匹配上了} else {dp[i][j] = dp[i][j - 1]; // 没匹配上}}}return dp[s_len][t_len] == s_len;}
};
48. 不同的子序列
115. 不同的子序列
思路:
dp[i][j]
表示以s[i-1]
结尾的字符串中包含以t[j - 1]
为结尾的字符串的个数- 递推公式:
- 匹配上了,即
s[i - 1] == t[j - 1]
,则可以利用之前匹配上的结果,不利用s[i - 1]
,两部分合起来就是目前的子序列数,dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
- 没匹配上,只能保持之前匹配上的子序列个数
dp[i][j] = dp[i - 1][j];
- 初始化,
dp[i][0] = 1
空串一定能在 s 中匹配到;dp[0][j] = 0
若 s 为空串,非空串一定在 s 中匹配不到- 遍历顺序从左上到右下
- 模拟图如下:
class Solution {
public:int numDistinct(string s, string t) {int s_len = s.length();int t_len = t.length();vector<vector<uint64_t>> dp(s_len + 1, vector<uint64_t>(t_len + 1, 0));for (int i = 0; i <= s_len; i++) dp[i][0] = 1;for (int i = 1; i <= s_len; i++) {for (int j = 1; j <= t_len; j++) {if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];else dp[i][j] = dp[i - 1][j];}}return dp[s_len][t_len];}
};