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

本是古典何须时尚 2022-05-23 13:28 144阅读 0赞

![这里写图片描述][70]

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));
        }
    }

[70]: /images/20220523/776b5e357615450199c10e9e56382ca0.png