signed

QiShunwang

“诚信为本、客户至上”

分割回文串 (dp)

2021/6/9 0:18:29   来源:

下定决心,好好过一天 ~
题目传送
思路:首先还是O(n2)的复杂度把,所有的回文子串都标记上,接下来就可以O(1)查询子序列i到j是否为回文串。接下来再来推另外一个动态方程。设pos[i]表示,以i位置结束的,子序列0到i最少可以分割为多少个符合条件的序列。那么从最开始递推,如果0到i本来就是回文,那么直接pos[i] = 0,否则。再来一个for,枚举位置j,判断j 到 i 是否为回文,如果为回文,那么维护最小值 pos[i] = min(pos[i] , pos[j-1] + 1),这个1就为j到i这个段的回文。

class Solution {
public:
    int minCut(string s) {
                int dp[2005][2005] = {0},len = s.size(),pos[2005];
    fill(pos,pos+2005,1e9+7);
    s = " " + s;
    for(int i = 1;i <= len;i++)
        dp[i][i] = 1;
    for(int i = 2;i <= len;i++)
    {
        for(int j = 1;j <= len;j++)
        {
            int l = j,r = j+i-1;
            if(l > r) continue;
            else if(r <= len && r == l+1 && s[l] == s[r])
            {
                dp[l][r] = 1;
            }
            else if(r <= len && s[l] == s[r] && dp[l+1][r-1])
            {
                dp[l][r] = 1;
            }
        }
    }
    for(int i = 1;i <= len;i++)
    {
        if(dp[1][i]) pos[i] = 0;
        else
        {
            for(int j = 1;j <= i;j++)
            {
                if(dp[j][i])
                {
                    pos[i] = min(pos[i],pos[j-1]+1);
                }
            }
        }
    }
    return pos[len];
    }
};