网站地图,海南搜索引擎优化,wordpress换背景插件,网站如何做导航条下拉菜单给你一个字符串 s#xff0c;请你将 s 分割成一些子串#xff0c;使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1#xff1a;
输入#xff1a;s “aab” 输出#xff1a;1 解释#xff1a;只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串…给你一个字符串 s请你将 s 分割成一些子串使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1
输入s “aab” 输出1 解释只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。 示例 2
输入s “a” 输出0 示例 3
输入s “ab” 输出1
提示
1 s.length 2000 s 仅由小写英文字母组成
解题思路
先用一次dp算出回文子串的位置信息 第二次使用最长递增子序列的思路计算出最少的切割次数
代码
class Solution {public int minCut(String s){int ns.length();boolean[][] dpnew boolean[n][n];for (int i n-1; i 0; i--) {for (int i1 i; i1 n; i1) {if(s.charAt(i)s.charAt(i1)){if(i1-i12)dp[i][i1]dp[i1][i1-1];elsedp[i][i1]true;}}}int[] resnew int[n];Arrays.fill(res,Integer.MAX_VALUE);for (int i 0; i n; i) {if(dp[0][i])//不用再切割{res[i]0;}else {for(int j0;ji;j)//遍历一次前面可能的切割位置找出最优的位置{if(dp[j1][i])res[i] Math.min(res[i],res[j]1);}}}return res[n-1];}
}
