LeetCode: Palindrome Partitioning I && II

思路分析

第一问就是个DFS水题，还是沿用LeetCode上面一贯的写法，传递引用来记录答案。这种难度的题目现在已经基本能够做到裸敲只要编译过就能1A的水平了。

第二问既然要求最优情况，显然就是DP。思路非常好想：使用dp[i]表示将前i个字符切分为回文串时，最少的切割次数，此时的状态转移方程是显然的。关键难度在于如何快速确定某个子串substr(i,j)是否为回文串？这其实也是个DP，使用dp[i][j]表示字符串从第i到第j个字符是否是回文串，则状态转移方程就有：dp[i][j] = s[i]==s[j]&&dp[i+1][j-1]，但是需要注意递推顺序，实在记不住可以上记忆化搜索。这个回文串的判定可以算作是经典问题了，最好记住。

代码

第二问

#define REP(i,a,b) for(int i=a;i<b;i++)
#define REV(i,a,b) for(int i=a-1;i>=b;i--)
#define rep(i,n) REP(i,0,n)
#define rev(i,n) REV(i,n,0)

class Solution {
public:
    bool dp[2000][2000];
    int minCut(string s) {
        if ( s.size() == 0 ) return 0;

        CLR(dp, 0);
        rev(i, s.size())
        REP(j, i, s.size()) {
            if ( i + 1 >= j - 1 ) dp[i][j] = (s[i] == s[j]);
            else dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1];
        }
        int *res = new int[s.size()];
        res[0] = 0;
        for ( int i = 1; i < s.size(); i++ ) {
            res[i] = INT_MAX;
            for ( int j = i; j >= 0; j-- ) if ( dp[j][i] ) {
                res[i] = min(res[i], j - 1 < 0 ? 0 : res[j - 1] + 1);
            }
        }
        return res[s.size() - 1];
    }
};