(代码随想录)132. 分割回文串 II(动态规划)

132. 分割回文串 II

这一题直接将我打回cv工程师的原型

除了dp还要定义一个辅助数组,用于表示 i 区间到 j 区间是否为回文串.

 动规五部曲

1.确定dp含义

dp[i]表示0到i之间的字符串需要切割的最小次数

2.确定递推公式

第一种就是0到i之间直接就是一个回文串,那么直接dp[i] = 0;跳过

第二种就是可以由[0, j]和[j + 1, i]两部分组成, 由于我们要求最小值,因此需要遍历[0, i]之间的j ,同时不停地求min值就行

3.初始化

dp数组由于需要疯狂地求min值,这里我把他设为每一个子串能切割的上限,即dp[i] = i;

4.j需要用到上一层i的值,因此i在外层,并从左到右遍历,j从0到i遍历

5.省了

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

动态规划还是好难[裂开]