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

Day57_动态规划

52. 回文子串

647. 回文子串
思路：

1. dp[i][j] 表示s[i~j]的字符串是否是回文串
2. 递推公式：如果 s[i] == s[j]，判断开区间 (i, j) 是不是回文串

• i == j 单个的字符都是回文串
• j - i == 1 以两个相同字符为中心的回文串
• dp[i+1][j-1] 长度超过3个回文串去掉首尾其内部也是回文串

3. 初始化，一开始初始化为每个字符串都不是回文串，然后开始遍历更新结果
4. 递推顺序：要用到下一行i+1的数据，所以递推在二维数组中从下往上，从左往右

class Solution {
public:
    int countSubstrings(string s) {
        int s_len = s.length();
        int ans = 0;
        vector<vector<bool>> dp(s_len, vector<bool>(s_len, false));
        for (int i = s_len - 1; i >= 0; i--) {
            for (int j = i; j < s_len; j++) {
                if (s[i] == s[j]) {
                    if (j - i <= 1) {
                        ans++;
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        ans++;
                    }
                }
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

53. 最长回文子序列

516. 最长回文子序列
思路：

子串必须是连续的，而这里的子序列可以不连续

1. dp[i][j] 表示 s[i~j] 中的最长回文子序列的长度
2. 递推公式

• s[i] == s[j] 全部加入回文串，使回文串长度加2，dp[i][j] = dp[i+1][j-1]+2
• s[i] != s[j] 选择一个让最大回文串更长的字符加入，dp[i][j] = max(dp[i+1][j], dp[i][j-1])

3. 初始化每个单个字符的为回文串，dp[i][j] = 1
4. 递推顺序从左下到右上

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int s_len = s.length();
        vector<vector<int>> dp(s_len, vector<int>(s_len, 0));
        for (int i = 0; i < s_len; i++) dp[i][i] = 1;
        for (int i = s_len - 1; i >= 0; i--) {
            for (int j = i + 1; j < s_len; j++) { // 单个字符已经初始化过了，这里直接从长度为2开始判断
                if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
                else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return dp[0][s_len - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15