本文共 1293 字，大约阅读时间需要 4 分钟。

class Solution {public:	int minCut(string s) {		// Start typing your C/C++ solution below		// DO NOT write int main() function		int len = s.size();		vector
   
     dp(len+1);//dp[i]: minimum cut between [i,len-1]		for(int i = 0; i <= len; ++i)			dp[i] = len-i;		vector
    
     
      > p;//p[i][j]: sub string [i,j] palindrome? 		p.resize(len);		for(int i = 0; i < len; ++i)			p[i].assign(len, false);		for (int i = len-1; i >= 0; --i)		{			for (int j = i; j < len; ++j)			{				if(s[i] == s[j] && (j-i < 2 || p[i+1][j-1]))				{					p[i][j] = true;					dp[i] = min(dp[i], 1+dp[j+1]);				}			}		}		return dp[0]-1;	}};
     
    
   

second time

class Solution {public:    int minCut(string s) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        int n = s.size();        if(n == 0) return 0;        vector
   
     f(n+1, INT_MAX);        f[0] = -1;        vector
    
     
       > p(n, vector
      
       (n, false));        for(int i = 0; i < n; ++i) p[i][i] = true;                for(int i = 1; i <= n; ++i)        {            for(int k = 0; k < i; ++k)            {                if(s[k] == s[i-1]) p[k][i-1] = (i-2 <= k+1) || p[k+1][i-2];                if(p[k][i-1]) f[i] = min(f[i], f[k]+1);            }        }        return f[n];    }};
      
     
    
   

转载地址：http://dmxti.baihongyu.com/