力扣 | 动态规划 | 在字符串的应用 | 最长回文子串、最长回文子序列、单词拆分、编辑距离

在解答字符串动态规划的应用时，我们需要非常注意一个问题：
  有时候我们定义$dp[i][j]$表示第一个字符串的第i个字符，第二个字符串的第j个字符。$dp[0][0]$表示两个都为空串时。
  使用数组下标访问时，应该这样访问第一个字符串的第i个字符：word1[i - 1]
  总的来说dp的定义可能和数组访问下标不一样。

if(word1[i - 1] == word2[j - 1])
	dp[i][j] = ···

我们还需要这样思考：为什么要使用动态规划？不使用其他方法？为什么动态规划可以解决？

1.最长回文子串

LeetCode：5.最长回文子串

一个回文串$str[i][j]$的子串有这样的性质：$str[i+1][j-1]$也是回文串。

因此我们要判断一个子串$str[i][j]$是否是回文串，我们只需要知道其子串$str[i+1][j-1]$是否是回文串即可。我们使用$dp[i][j]$保存该区间[i,j]是否是回文串。

这样我们就使用回文字符串常用的解题方式——从长度为1的子串开始判断是否为回文串，判断完后长度加一，这样每次都能保证判断时，其子串都已经知道是否是回文串了。

时间复杂度：$O(n^2)$

class Solution {
public:
    string longestPalindrome(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));//dp[i]表示以i结尾的 最长回文子串
        dp[0][0] = true;
        
        int left = 0, len = 1;
        for(int j = 1; j < s.size(); ++ j){
            int tmp = j - 1;
            dp[j][j] = true;
            if(s[tmp] == s[j]) {dp[tmp][j] =true;left = tmp; len = 2;}
        }
        for(int i = 2; i < s.size(); ++ i){//距离
            for(int j = i; j < s.size(); ++ j){
                int tmp = j - i;
                if(s[j] == s[tmp] ){
                    if(dp[tmp + 1][j - 1] == true) {dp[tmp][j] = true;left = tmp; len = i + 1;}
                }
            }
        }

        return s.substr(left, len);
    } 
};

2.最长回文子序列

LeetCode：2.最长回文子序列

与最长回文子串类似，本题的区别是，不要求子串严格是回文串，只需要包含回文串即可。

因此我们要判断一个子串$str[i][j]$是否包含回文串，我们只需要知道其子串$str[i+1][j-1]$是否包含回文串即可。我们使用$dp[i][j]$保存该区间[i,j]是包含的最长回文串长度。

时间复杂度：$O(n^2)$

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.length();
        if(n == 1) return 1;
        vector<vector<int>> dp(n, vector<int>(n));
        for(int i = 0; i < n; ++ i) {dp[i][i] = 1;}

        for(int i = 1; i < n; ++ i){
            for(int j = i; j < n; ++ j){
                int l = j - i;
                char c1 = s[l], c2 = s[j];
                if(c1 == c2){
                    dp[l][j] = dp[l + 1][j - 1] + 2;
                }else{
                    dp[l][j] = max(dp[l][j - 1], dp[l + 1][j]);
                }
            }
        }
        return dp[0][n - 1];
    }
};

3.单词拆分

LeetCode：139. 单词拆分

这个拼接的顺序不是随便的，比如$catsand$，字典为$["cat"，"cats"，"and"]$，如果先用$"cat"$去拼接，会导致问题无解，但实际上有解。

定义$dp[i]$表示，前$i$个字符是否可以被拼接，那么它能被拼接的话，我们用字典里面的词一个一个放到末尾，然后看$dp[i-dict.size()]$能否被拼接就能知道$dp[i]$能否被拼接了。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for(int i = 1; i <= s.size(); ++ i)
            for(auto & str : wordDict)
                if(str.size() <= i && dp[i - str.size()] == true)
                    if(s.substr(i - str.size(), str.size()) == str){
                        dp[i] = true;
                        break;
                    }

        return dp[s.size()];
    }
};

4.编辑距离

LeetCode：72.编辑距离

其实动态规划问题就是思考出状态以及状态转移，比如这里你想要知道$word1$到$word2$转换次数，你就只需要知道其子串。

if(word1[i - 1] == word2[j - 1]){
    dp[i][j] = dp[i - 1][j - 1];
}else{
    dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
}

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));

        for(int i = 1; i <= word1.size(); ++ i){
            dp[i][0] = i;
        }
        for(int i = 1; i <= word2.size(); ++ i){
            dp[0][i] = i;
        }

        for(int i = 1; i <= word1.size(); ++ i){
            for(int j = 1; j <= word2.size(); ++ j){
                if(word1[i - 1] == word2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                }
            }
        }

        return dp[word1.size()][word2.size()];
    }
};

5. 共同点和思路

这些字符串相关的动态规划问题有一些共同的特点：

1. 定义状态：

   • 使用二维数组 dp 表示两个子串之间的某种状态（如是否回文、最长子序列长度、是否可以拼接、编辑距离等）。

2. 状态转移：

   • 根据问题的具体要求，定义状态转移方程，用子问题的解构建原问题的解。

3. 初始化：

   • 根据问题的初始条件，初始化 dp 数组的边界值。

4. 遍历顺序：

   • 通常使用双重循环遍历所有可能的子串或子序列。

6. 各个问题的思路和扩展

1. 最长回文子串

思路：

• 定义 dp[i][j] 表示字符串 s 从第 i 到第 j 的子串是否为回文串。
• 如果 s[i] == s[j]，并且 dp[i+1][j-1] 为真，则 dp[i][j] 为真。
• 初始化单个字符的子串和长度为2的子串。

扩展：

• 可以使用中心扩展法来优化时间复杂度，从每个字符和字符间隙向两边扩展检查回文。

2. 最长回文子序列

思路：

• 定义 dp[i][j] 表示字符串 s 从第 i 到第 j 的子串中最长回文子序列的长度。
• 如果 s[i] == s[j]，则 dp[i][j] = dp[i+1][j-1] + 2。
• 否则，dp[i][j] = max(dp[i+1][j], dp[i][j-1])。

扩展：

• 可以尝试空间优化，将二维数组优化为一维数组。

3. 单词拆分

思路：

• 定义 dp[i] 表示字符串 s 的前 i 个字符能否被拆分成字典中的单词。
• 对于每个位置 i，检查从 j 到 i 的子串是否在字典中，并且 dp[j] 是否为真。

扩展：

• 可以使用记忆化搜索或递归的方法来优化复杂度。

4. 编辑距离

思路：

• 定义 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数。
• 如果 word1[i-1] == word2[j-1]，则 dp[i][j] = dp[i-1][j-1]。
• 否则，dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。

扩展：

• 可以尝试空间优化，将二维数组优化为一维数组。
• 可以扩展到其他字符串变换问题，如最长公共子序列。