class Solution {
public:
    int result_num = INT_MAX;
    void trak_back(vector<vector<bool>> &dp , int indnx ,int result)
    {
        if(indnx == dp[0].size())
        {
            if(result_num > result) result_num = result;
            return;
        }
        for(int i=0 ; i<dp[0].size() ;i++)
        {
            if(dp[indnx][i] == true )
            {
                trak_back(dp,i+1,result+1);
            }
        }
    }
    int minCut(string s) {
        int result =0;
        vector<vector<bool>> dp(s.size() , vector<bool>(s.size(),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|| dp[i+1][j-1] == true )) dp[i][j] = true;
            }
        }
        trak_back(dp,0,result);
        return result_num-1;
    }
};

class Solution {
public:
    int minCut(string s) {
        vector<vector<bool>> dp(s.size() , vector<bool>(s.size(),false)); //dp[i][j]为i到j内是否是回文子串
        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|| dp[i+1][j-1] == true )) dp[i][j] = true;
            }
        }
       vector<int> dp2(s.size() , 0); //dp2[i] 为i内最少可以分为几段
       for(int i=0 ; i<s.size() ;i++) dp2[i] = i+1;//初始化，最差的情况，一个字符一段
       for(int i=0 ; i<s.size() ;i++) 
       {
            if(dp[0][i] == true)  //如果0到i是一段，则不看0到i内部，直接dp2[i] = 1；
            {
                dp2[i] = 1;
                continue;
            }
            for(int j=0 ; j<i ;j++) //判断j+1 到 i是否是一段，如果是 在dp2[i] 和 dp[j]+1选最小
                if(dp[j+1][i] == true) dp2[i] = min(dp2[i] , dp2[j] + 1 );
       }
        return dp2[s.size()-1] - 1;
    }
};