C++刷LeetCode（132. 分割回文串 II）【动态规划】
本帖最后由 糖逗 于 2020-7-8 12:45 编辑题目描述：
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的最少分割次数。
示例:
输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
class Solution {
public:
bool valid(string & s, int i , int j){//验证是回文
int left = i, right = j;
while(left < right){
if(s != s)return false;
left++;
right--;
}
return true;
}
int minCut(string s) {
int len = s.size();
if (len < 2)return 0;
vector<int> dp(len, 0);
for(int i = 0; i < len; i++)dp = i;
for(int i = 1; i < len ;i++){
if (valid(s, 0, i)){
dp = 0;
continue;
}
for(int j = 0; j <= i; j++){
if(valid(s, j + 1, i)){
dp = min(dp, dp + 1);
}
}
}
return dp;
}
};
参考链接：https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/dong-tai-gui-hua-by-liweiwei1419-2/
页:
[1]