1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Solution {
public:
    int ans;
    int minCut(string s) {
        ans = 0xffffff;
        if(s.length() <= 0)return ans;
        bool *flag = new bool[s.length()+1];
        for(int i = 0;i <= s.length();i++)
            flag[i] = false;
        flag[0] = true;
        PartitionStep(s,1,flag);
        return ans;
    }
private:
    void PartitionStep(string s,int step,bool *flag) {
        if(step == s.length()) {
            int i;
            flag[step] = true;
            for(i = step-1;i >= 0;i--) {
                if(flag[i] == true)break;
            }
            if(IsPalindrome(s,i,step-1)) {
                int count = 0;
                for(int i = 0;i <=step;i++) {
                    if(flag[i] == true)count++;
                }
                if(count-2 < ans)ans = count-2;
            }
            flag[step] =false;
            return ;
        }
        flag[step] = true;
        int i;
        for(i = step-1;i >= 0;i--) {
            if(flag[i] == true)break;
        }
        if(IsPalindrome(s,i,step-1)) {
            PartitionStep(s,step+1,flag);
        }
        flag[step] = false;
        PartitionStep(s,step+1,flag);
    }
    bool IsPalindrome(string s,int i,int j) {
        while(i < j) {
            if(s[i] != s[j])return false;
            i++;
            j--;
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    int minCut(string s) {
        int lens = s.length();
        bool **isP;
        isP = new bool *[lens];
        for(int i = 0;i < lens;i++) {
            isP[i] = new bool [lens];
            for(int j = 0;j < lens;j++) {
                isP[i][j]  = false;
            }
        }
        for(int i = 0;i < lens;i++)
            isP[i][i] = true;

        int * dp = new int[lens+1];
        for(int i = lens;i >= 0;i--)
            dp[i] = lens - 1 - i;
        for(int i = lens-1;i >= 0;i--) {
            for(int j = i;j < lens;j++) {
                if(((j - i) <= 2 || isP[i+1][j-1]) && s[i] == s[j]) {
                    isP[i][j] = true;
                    dp[i] = dp[i] > dp[j+1]+1?dp[j+1]+1:dp[i];
                }
            }
        }
        return dp[0];
    }
};