【十三】【动态规划】1745. 分割回文串 IV、132. 分割回文串 II、516. 最长回文子序列，三道题目深度解析

动态规划

动态规划就像是解决问题的一种策略，它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题，并将每个小问题的解保存起来。这样，当我们需要解决原始问题的时候，我们就可以直接利用已经计算好的小问题的解，而不需要重复计算。

动态规划与数学归纳法思想上十分相似。

数学归纳法：

1. 基础步骤（base case）：首先证明命题在最小的基础情况下成立。通常这是一个较简单的情况，可以直接验证命题是否成立。

2. 归纳步骤（inductive step）：假设命题在某个情况下成立，然后证明在下一个情况下也成立。这个证明可以通过推理推断出结论或使用一些已知的规律来得到。

通过反复迭代归纳步骤，我们可以推导出命题在所有情况下成立的结论。

动态规划：

1. 状态表示：

2. 状态转移方程：

3. 初始化：

4. 填表顺序：

5. 返回值：

数学归纳法的基础步骤相当于动态规划中初始化步骤。

数学归纳法的归纳步骤相当于动态规划中推导状态转移方程。

动态规划的思想和数学归纳法思想类似。

在动态规划中，首先得到状态在最小的基础情况下的值，然后通过状态转移方程，得到下一个状态的值，反复迭代，最终得到我们期望的状态下的值。

接下来我们通过三道例题，深入理解动态规划思想，以及实现动态规划的具体步骤。

1745. 分割回文串 IV - 力扣（LeetCode）

题目解析

状态表示

状态表示通常由经验+题目要求得到，

经验一般指以某个位置为结尾，或者以某个位置为开始。

我们需要判断（i，j）子数组是否属于回文子数组，可以定义dp[i][j]表示（i，j）子数组是否属于回文子数组。

状态转移方程

我们希望（i，j）位置的状态能够通过其他位置的状态推导出来。

针对于（i，j）位置的状态进行分析。

1. 如果nums[i]==nums[j]，

   1. 如果（i，j）子数组只有一个元素，即i==j， 只有一个元素属于回文子数组情况，故dp[i][j]=true。

   2. 如果（i，j）子数组只有两个元素，即i+1==j， 此时符合回文子数组的定义，故dp[i][j]=true。

   3. 如果（i，j）子数组有3个或3个以上的元素，即i+1<j, 此时，如果(i+1,j-1)子数组可以构成回文子数组，那么（i，j）子数组就可以构成回文子数组。 故，dp[i][j]=dp[i+1][j-1]。

2. 如果nums[i]!=nums[j]， 此时不可能构成回文子数组，所以dp[i][j]=false。

对上述情况进行合并和简化，

如果我们对所有位置状态初始化为false，我们就只需要判断nums[i]==nums[j]的情况，

此时的状态转移方程为，

       if(s[i]==s[j]){
               dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
       }

初始化

根据状态转移方程，我们知道推导（i，j）位置的状态时，可能需要用到dp[i+1][j-1]位置的状态， 如果i+1<j,此时需要保证（i+1，j-1）对应下标不会越界，并且此时（i+1，j-1）位置状态已经填写完毕。

先考虑填表顺序，我们知道i介于（0，n-1）之间，j介于（i，n-1）之间，所以i+1介于（1，n）之间且i+1<j，所以i+1介于（1，n-1）之间，i+1不会越界。

又j介于（i，n-1）之间，j-1介于（i-1，n-2）之间，又j-1>i，所以j-1也不会越界。

要保证此时（i+1，j-1）位置状态已经填写完毕，只需要控制填报顺序即可。

所以我们需要初始化所有位置状态为false即可，也就是在状态转移方程中分析的初始化。

填表顺序

根据状态转移方程，我们知道推导（i，j）位置的状态时，可能需要用到dp[i+1][j-1]位置的状态， 所以在填写（i，j）位置状态时，需要保证（i+1，j-1）位置状态已经填写完毕。

1. 如果固定i填写j， 那么i的变化一定要从大到小，此时当我们填写（i，j）位置的状态时，（i+1，）位置的状态已经填写完毕，所以j的变化可以从大到小也可以从小到大。

2. 如果固定j填写i， 那么j的变化一定要从小到大，此时当我们填写（i，j）位置的状态时，（，j-1）位置的状态已经填写完毕，所以i'的变化可以从大到小也可以从小到大。

如果我们选择固定i填写j，得到

    for(int i=n-1;i>=0;i--){
            for(int j=i;j<=n-1;j++){
            
            }
    }

返回值

dp[i][j]表示（i，j）子数组是否属于回文子数组。

dp状态的填写只完成了第二步的工作，即快速判断（i，j）子数组是否为回文子数组。

还有一步，就是使（a，b）遍历所有情况。

如果有一种情况三部分都是回文子数组，就返回true，否则就返回false。

代码实现

class Solution {
public:
    bool checkPartitioning(string s) {

        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        for (int i = n - 1; i >= 0; i--)
            for (int j = i; j < n; j++)
                if (s[i] == s[j])
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;

        for (int i = 1; i < n - 1; i++)
            for (int j = i; j < n - 1; j++)
                if (dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1])
                    return true;
        return false;
    }
};

132. 分割回文串 II - 力扣（LeetCode）

题目解析

状态表示

状态表示通常由经验+题目要求得到，

经验一般指以某个位置为结尾，或者以某个位置为开始。

我们很容易可以定义这样一个状态表示，定义dp[i]表示在（0，i）区间上的字符串，最少的分割次数。

状态转移方程

我们针对于最后一个位置的状态进行分析，看看i位置状态能不能由其他位置的状态推导得出，定义0<=j<=i，那我们可以根据（j，i）位置上的子串是否是回文串分成下面两种情况，

1. 如果（j，i）可以构成回文串， i位置的状态就等于j-1位置上的状态+1，即dp[i]=dp[j-1]+1。

2. 如果（j，i）不能构成回文串， 此时j的位置不需要考虑。

因为dp[i]要的是最小的分割次数，所以j需要遍历（0~i-1）。

因为我们需要快速判断（j，i）位置是否属于回文字符串，所以我们可以先创建一个dp表，dp[i][j]表示（i，j）字符串是否构成回文字符串。用来存储是否可以构成回文字符串的信息。

根据上述分析，我们知道要推导i位置的状态，可能需要用到j-1位置的状态。

所以i的变化应该是从小到大，即（0~n-1）。

令j-1>=0得j>=1，只有j>=1的时候才不会越界。所以我们需要控制j介于（1，i）之间。

独立判断（0，i）这种情况。

所以状态转移方程为，

        for (int i = 0; i < n; i++) {
            if (isPal[0][i])
                dp[i] = 0;
            else {
                for (int j = 1; j <= i; j++)
                    if (isPal[j][i])
                        dp[i] = min(dp[i], dp[j - 1] + 1);
            }
        }

初始化

带入最初始的推导，即i=0，发现dp[i] 可以正常推导，而后续的状态都可以根据前面已经推导的状态进行推导得出，所以不需要进行初始化。

填表顺序

从左往右

返回值

dp[i]表示在（0，i）区间上的字符串，最少的分割次数。

题目要求我们找到（0，n-1）区间上的字符串，最少的分割次数，

所以返回dp[n-1]即可。

代码实现

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<vector<bool>> isPal(n, vector<bool>(n));
        for (int i = n - 1; i >= 0; i--)
            for (int j = i; j < n; j++)
                isPal[i][j] = s[i] == s[j] ? (i + 1 < j ? isPal[i + 1][j - 1] : true): false;
        vector<int> dp(n, INT_MAX);
        for (int i = 0; i < n; i++) {
            if (isPal[0][i])
                dp[i] = 0;
            else {
                for (int j = 1; j <= i; j++)
                    if (isPal[j][i])
                        dp[i] = min(dp[i], dp[j - 1] + 1);
            }
        }
        return dp[n - 1];
    }
};

516. 最长回文子序列 - 力扣（LeetCode）

题目解析

状态表示

状态表示一般通过经验+题目要求得到，

经验一般指以某个位置为结尾，或者以某个位置为开始。

题目要求我们找回文子序列，根据以前的经验，和回文有关的问题，我们的状态表示研究的对象一

般都是选取原字符串中的一段区域[i,j]内部的情况来研究。

所以我们可以定义dp[i][j]表示s字符串[i,j]区间内所有子序列中，最长的回文序列长度。

状态转移方程

我们针对于最后一个位置的状态进行分析，看看i位置状态能不能由其他位置的状态推导得出。

如果紫色的字符串可以构成回文串，那么我们在紫色字符串两端添加相同的蓝色元素，整个字符串同样可以构成回文串。

根据这种思维，我们可以根据i，j两个位置的元素是否相等进行分析。

1. 如果s[i]==s[j]， 那么[i，j]区间上的最长回文子序列，应该是 [i+1,j-1] 区间上的最长回文子序列首尾加上s[i],s[j]两个元素，此时dp[i][j]=dp[i+1][j-1]+2。

2. 如果s[i]!=s[j]， 说明[i,j]区间上的回文子序列不可能同时取到i,j两个位置上的元素。

   1. 如果i位置元素不取， 此时[i,j]区间上的最长回文子序列的长度，应该是[i+1,j]区间上的最长回文子序列的长度。即dp[i][j]=dp[i+1][j]。

   2. 如果j位置元素不取, 此时[i,j]区间上的最长回文子序列的长度，应该是[i,j-1]区间上的最长回文子序列的长度。即dp[i][j]=dp[i][j-1]。

第二种情况下，dp中存储的是最长的回文子序列的长度，所以dp[i][j]=max(dp[i+1][j],dp[i][j-1])。

综上所述，状态转移方程为，

s[i] == s[j] 时: dp[i][j] = dp[i + 1][j - 1] + 2 s[i] != s[j] 时: dp[i][j] = max(dp[i][j - 1],dp[i + 1][j])

初始化

根据状态转移方程，我们知道想要推导（i，j）位置的状态，可能需要用到（i+1，j-1），（i，j-1），（i+1，j）位置上的状态。

我们先判断填表顺序，

1. 如果固定i改变j， 那么i的变化一定从大到小，因为可能用到（i，j-1）位置的状态，所以j的变化需要从小到大。

2. 如果固定j改变i， 那么j的变化一定从小到大，因为可能用到（i+1，j）位置的状态，所以i的变化需要从大到小。

所以我们可以得到完整的状态转移方程，

        for (int i = n - 1; i >= 0; i--)
        {
            dp[i][i] = 1;                   
            for (int j = i + 1; j < n; j++)
            {
              
                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]);
            }
        }

我们把最初迭代情况带入迭代代码中，即i=n-1，j=n，此时得到dp[n-1][n-1]=1。

而后续的状态都可以根据前面的状态推导得出，所以我们不需要进行初始化。

填表顺序

1. 如果固定i改变j， 那么i的变化一定从大到小，因为可能用到（i，j-1）位置的状态，所以j的变化需要从小到大。

2. 如果固定j改变i， 那么j的变化一定从小到大，因为可能用到（i+1，j）位置的状态，所以i的变化需要从大到小。

返回值

dp[i][j]表示s字符串[i,j]区间内所有子序列中，最长的回文序列长度。

根据题目要求，我们需要得到[0,n-1]区间内所有子序列中，最长的回文子序列长度。

所以返回dp[0][n-1]。

代码实现

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n)); 

        for (int i = n - 1; i >= 0; i--)
        {
            dp[i][i] = 1;                   
            for (int j = i + 1; j < n; j++)
            {
              
                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][n - 1];
    }
};

结尾

今天我们学习了动态规划的思想，动态规划思想和数学归纳法思想有一些类似，动态规划在模拟数学归纳法的过程，已知一个最简单的基础解，通过得到前项与后项的推导关系，由这个最简单的基础解，我们可以一步一步推导出我们希望得到的那个解，把我们得到的解依次存放在dp数组中，dp数组中对应的状态，就像是数列里面的每一项。最后感谢您阅读我的文章，对于动态规划系列，我会一直更新，如果您觉得内容有帮助，可以点赞加关注，以快速阅读最新文章。

最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。

同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。

谢谢您的支持，期待与您在下一篇文章中再次相遇！