随想录一刷Day55——动态规划

Day55_动态规划

47. 判断子序列

392. 判断子序列
思路：

双指针很简单，$O(n)$ 时间就能解决
这里还是用dp

1. dp[i][j] 表示以 s[i - 1] 结尾的字符串和以 t[]i-1 为结尾的字符串的最大子序列长度
2. 地推公式

• 如果匹配上了，即 s[i - 1] == t[j - 1] ,则从上一次的子序列长度加1， dp[i][j] = dp[i - 1][j - 1] + 1;
• 没匹配上，则 dp[i][j] = dp[i][j - 1]; 则保留上次的子序列长度，继续向后匹配 t

3. 初始化，如图，初始化来自左上角和左边，初始化 dp[0][0] 和 dp[i][0] 为 0
   
   
4. 遍历顺序：遍历顺序是从左上到右下，外层是 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

48. 不同的子序列

115. 不同的子序列
思路：

1. dp[i][j] 表示以 s[i-1] 结尾的字符串中包含以 t[j - 1] 为结尾的字符串的个数
2. 递推公式：

• 匹配上了，即 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];

3. 初始化，dp[i][0] = 1 空串一定能在 s 中匹配到；dp[0][j] = 0 若 s 为空串，非空串一定在 s 中匹配不到
4. 遍历顺序从左上到右下
5. 模拟图如下：
   

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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16