字符串最小切割次数，实现获得子串都为回文串

本文主要是介绍字符串最小切割次数，实现获得子串都为回文串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这里写图片描述

public class Solution {/**解题思路：动态规划问题(动态规划的题，最主要就是写出状态转移方程)。dp[i] - 表示子串（0，i）的最小回文切割，则最优解在dp[s.length-1]中。分几种情况：1.初始化：当字串s.substring(0,i+1)(包括i位置的字符)是回文时，dp[i] = 0(表示不需要分割)；否则，dp[i] = i（表示至多分割i次）;2.对于任意大于1的i，如果s.substring(j,i+1)(j<=i,即遍历i之前的每个子串)是回文时，dp[i] = min(dp[i], dp[j-1]+1);3.如果s.substring(j,i+1)(j<=i)不是回文时，dp[i] = min(dp[i],dp[j-1]+i+1-j);*///动态规划:最小切割次数，实现获得子串都为回文串public int minCut(String s) {if(s==null||s.length()==0)return 0;if(isHui(s))return 0;int[]dp=new int[s.length()]; //动态规划表for(int i=0;i!=s.length();i++){dp[i]=isHui(s.substring(0,i+1))?0:i;if(dp[i]==0)continue;for(int j=1;j!=i+1;j++){if(isHui(s.substring(j,i+1))){dp[i]=Math.min(dp[i],dp[j-1]+1);}else{dp[i]=Math.min(dp[i],dp[j-1]+i+1-j);}}}return dp[s.length()-1];}//判断是否为回文串private boolean isHui(String s){int i=0;int j=s.length()-1;while(i!=j&&i!=s.length()&&j!=-1){if(s.charAt(i)!=s.charAt(j)){return false;}else{i++;j--;}}return true;}public static void main(String[]args){//System.out.println("Hello World！");String s="leet";Solution sol=new Solution();System.out.println(sol.minCut(s));}
}