开发网页的常用软件_怀柔区企业网站设计机构提供_开发小程序_优化建站seo门户

思路：快速判断回文串的代码注意i和j所在的位置，因为是从i到j的，因此i在第二个循环，求最少分割次数时要注意是否初始就行，然后在枚举分割点

AC代码：

class Solution {
public:int minCut(string s) {int n = s.size();//i-j之间是否为回文串vector<vector<int>>dp(n + 2, vector<int>(n + 2));for(int j = 1; j <= n; j ++){for(int i = j; i >= 1; i --){if(i == j) dp[i][j] = 1;else {if(j-  i + 1 == 2){dp[i][j] = (s[i - 1] == s[j - 1]);}else {dp[i][j] = (s[i - 1] == s[j - 1] && dp[i + 1][j - 1]);}                  }}}//记录1-r满足条件的所需要的最少的分割次数vector<int>f(n + 1, 1e5);for(int r = 1; r <= n; r ++){if(dp[1][r]) f[r] = 0;//说明已经满足是回文了else {f[r] = r - 1;for(int l = 1; l <= r; l ++){if(dp[l][r]){f[r] = min(f[r], f[l - 1] + 1);}}}}return f[n];}
};