分割回文串-ii

public class Solution {
      /**
     * 回文的最小分割数
     * 1.dp[i]表示当前i到len-1这段的最小分割数
     * 2.dp[i]=min{dp[j+1]+1}（i=<j<len）其中str[i..j]必须是回文、
     * 3.p[i][j]=true表示str[i..j]是回文
     * 4.p[i][j]=s.charAt(i)==s.charAt(j) && (j-i<2||p[i+1][j-1])
     */
    public int minCut(String s) {
        int []dp=new int[s.length()+1];
        boolean [][]p=new boolean[s.length()][s.length()];
        dp[s.length()]=-1;//确保dp[s.length()-1]=0
        for(int i=s.length()-1;i>=0;i--){
            dp[i]=Integer.MAX_VALUE;
            for(int j=i;j<s.length();j++){
                if(s.charAt(i)==s.charAt(j) && (j-i<2||p[i+1][j-1])){
                    p[i][j]=true;
                    dp[i]=Math.min(dp[i],dp[j+1]+1);
                }
            }
        }
        return dp[0];
    }
}

/**

* 动态规划的题，最主要就是写出状态转移方程
* 状态转移，其实就是怎么把一个大的状态表示为两个或者多个已知的状态
* 以此题为例，设f[i][j]为最小的切点数，那么有：
* 1、s[i][j]为回文字符串，则f[i][j] = 0;
* 2、增加一个切点p，将s[i][j]切割为两端s[i][p]、s[p+1][j],则f[i][j] = f[i][p]+f[p+1][j]
* 所谓的状态转移方程就是上面的式子
*
* 接着来看看怎么组织程序，先看看状态转移的思路：
* 以"aab"为例，"aab"明显不是回文串
* 所以 f("aab") = min( (f("a")+f("ab")) , (f("aa")+f("b")) ) + 1;
* f("a") = 0;
* f("ab") = f("a")+f("b") +1  = 0+0+1 = 1;
* f("aa") = 0;
* f("b") = 0;
* 即f("aab") = 1;
*
* 聪慧的你一定能看出来，这是一个递归调用的过程，计算f("ab")需要先计算f("a")、f("b")
* 用递归实现动态规划，在思路上是最简单的，大部分的题目都可以用这种方式解决
*
* 但是有一些数据变态的题目，加上测试机子给的堆栈太小，这种递归的算法很容易就爆栈了
* 我们需要用我们的聪明智慧，把递归的程序写为非递归的。
* 把解题思路从下往上看，假设我们先求出来了f("a")，f("b")
* 那么我们可以求出f("aa"),f("ab")
* 接着我们就可以得出答案f("aab")了
* 在这个过程中，我们需要牺牲空间（f[1000][1000]）代替堆栈记录递归调用的返回值
* 而且这种方式有个好处，就是可以减少计算量
* 比如计算f("aab")时需要计算f("aa")+f("b")
* 计算f("ab")事需要计算f("a")+f("b")
* 这里就计算了两次f("b");
* 在第一次计算f("b")之后,将f("b")记录下来，可以减少一次计算量
* 动态规划本质上是暴力搜索，只不过咋这个暴力搜索的过程中，减少了不必要的计算，这样就提升了算法解决问题的速度
* 在一些题目中，你还可以根据题目减少某些分支的计算
* 比如只要判断这个字符串是回文串，就可以直接返回0，不需要一步步计算其中的子序列
*
* 写给亲爱的啊呆少女
*/

public class Solution {
private String s;
private int f[][] = new int[1000][1000];

public int minCut(String s) {
this.s = s;
//先求解小段的子序列
for(int t=0;t<=s.length();t++){
for(int i=0,j=t;j<s.length();i++,j++){
f[i][j] = compCut(i,j);
}
}
return f[0][s.length()-1];
}

// 状态转移方程的实现
public int compCut(int i,int j) {
if(isPalindrome(i,j)) return 0;
int min = s.length();
for(int p=i;p<j;p++) {
int a = f[i][p];
int b = f[p+1][j];
a = a + b + 1;
min = min<a?min:a;
}
return min;
}

//判断是否回文串
public boolean isPalindrome(int i,int j){
while(i<j) {
if(s.charAt(i) != s.charAt(j))
return false;
i++;
j--;
}
return true;
}
}

  解题思路：动态规划问题。
    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 static int minCut(String s) {
        int[] dp = new int[s.length()];
        for(int i=0;i<s.length();i++){
        	dp[i] = isPalindrome(s.substring(0, i+1))?0:i;
        	if(dp[i] == 0)
        		continue;
        	for(int j=1;j<=i;j++){
        		if(isPalindrome(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[dp.length-1];
    }

    //判断回文
    public static boolean isPalindrome(String s){
    	boolean flag = true;
    	for(int i=0,j=s.length()-1;i<j;i++,j--){
    		if(s.charAt(i) != s.charAt(j)){
    			flag = false;
    			break;
    		}
    	}
    	return flag;
    }

/**
* 动态规划：回文的最小切割数
* 题意： 给定一个字符串s，返回把s全部切成回文子串的最小分割数。
*        例如"ABA"，不需要切割，返回0；"ABCBAE"，需要切割1次，成"ABCBA"和"E"，返回1。
*        "ABCDE"，需要切割4次，变成"A"、"B"、"C"、"D"、"E"，返回4。
*
* 解：
* dp[i]表示s.substring(0, i + 1)子串的回文最小切割数，
* (Java子字符串函数满足左闭右开特点，i+1表示包含第i个字符)
* 显然最终结果为dp[s.length - 1]。
* 
* 确认初始状态：
*    dp[0] = 0,1个字符不用切割
*    当子串是回文串时，dp[i] = 0， 
*    否则dp[i]初值等于i（最坏的情况），
*    即整个子串不存在回文子字符串，需要切割i次成单个字符
* 确认状态转移方程：
*    当s.substring(j, i + 1) (1 <= j <= i)是回文时，
*    dp[i] = min(dp[i], dp[j - 1] + 1)。
*    即用变量j遍历i之前的每个子串，注意判断是否回文，是则重新给dp[i]赋值
*
* （小白一枚，借鉴了网友的思路，自己总结了一下）
**/
public class Solution {
    public int minCut(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] dp = new int[s.length()];
        dp[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            dp[i] = isPalindrome(s.substring(0, i + 1)) ? 0 : i;
            if (dp[i] != 0) { //dp[i] = 0时不需要内循环
                for (int j = i; j > 0; j--) {
                    if (isPalindrome(s.substring(j, i + 1))) {
                        dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                    }
                }
            }
        }
        return dp[s.length() - 1];
    }
    
    private static boolean isPalindrome(String s) {
        int begin = 0;
        int end = s.length() - 1;
        while (begin < end) {
            if (s.charAt(begin++) != s.charAt(end--)) {
                return false;
            }
        }
        return true;
    }
    
}

定义动态规划数组dp，dp[i]的含义是子串str[0…i]至少需要切割几次，才能把str[0…i]全部切成回文子串。那么dp[len-1]就是最后的结果。

从左往右依次计算dp[i]的值，i 初始为0，具体计算过程如下：

1、假设 j 处在 0 到 i 之间，如果str[j…i]是回文串，那么dp[i]的值可能是dp[j-1] + 1，其含义是在str[0…i]上，既然str[j…i]是回文串，那么它可以自己作为一个分割的部分，剩下的部分str[0…j-1]继续做最经济的分割，也就是dp[j-1]的值。

2、根据步骤1的方式，让 j 在 i 到 0 的位置上枚举，那么所有可能中最小值就是dp[i]的值，即dp[i] = min{dp[j-1]+1 (0<= j <= i，且str[j…i]必须是回文串)}。

3、如何快速方便的判断str[j…i]是否为回文串？

　1）定义一个二维数组p，如果p[j][i]为True，表示str[j…i]是回文串，否则不是。在计算dp过程中，希望能够同步、快速的计算出矩阵p。

　2）p[j][i]如果为True，一定来自以下三种情况：
　　
　　<1>　str[j][i]由一个字符组成
　　<2>　str[j][i]由两个字符组成且两个字符相等
　　<3>　str[j][i]由多个字符组成，str[j] == str[i]且p[j+1][i-1] == True。

　3）在计算dp数组的过程中，位置i是从左向右依次计算的。而对于每一个i来说，又依次从 i 位置向左遍历所有的位置，以此来决策dp[i]。所以对于p[j][i]来说，p[j+1][i-1]一定已经计算过。

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        if(n < 2)
            return 0;
        vector<int> dp(n, INT_MAX);
        vector<bool> tmp(n, false);
        vector<vector<bool> > p(n, tmp);
        for(int i=0; i<n; i++)
        {
            for(int j=i; j>-1; j--)
            {
                if(s[i] == s[j] && (i-j < 2 || p[j+1][i-1]))
                {
                    p[j][i] = true;
                    dp[i] = min(dp[i], j == 0? 0 : dp[j-1] + 1);
                }
            }
        }
        return dp.back();
    }
};

class Solution {
public:
    // 使用动态规划来做    0,1,...,i,i+1,...,j,j+1 ,如果i~j是回文，则cut[j+1] = min(cut[j+1],cut[i]+1)
    int minCut(string s)
    {
        int len = s.length();
        vector<int> minCuts(len+1);
        for(int i=0;i<=len;i++)
           minCuts[i] = i-1;
         bool dp[len][len];
        fill_n(&dp[0][0],len*len,false);
        for(int j=1;j<len;j++)
        {
            for(int i=j;i>=0;i--)
            {
                if(s[i] == s[j] && (dp[i+1][j-1] || (j-i)<2))
                {
                   dp[i][j] = true;
                   minCuts[j+1] = min(minCuts[j+1],1+minCuts[i]);
                }    
            }
        }
       return minCuts[len]; 
    }
};

每次这类问题都要搞好半天... 个人感觉动归问题最难在于分析出状态转移方程。

对该问题稍加分析不难的得到如下思路：
定义f（i，j）表示字符串区间[i,j]的最小cut数目，于是转移方程为： f(i,j) = min{ f(i,k)+f(k+1,j)+1}, 0<=i <=k<j <len
1. 基于这样的思路，可以得出下面递归代码：

int minCut(string s) {
     if(isPalindrome(s)) return 0;
     set st;
     for(int i=1; i< s.size(); ++i){
        string w = s.substr(0,i);
        string left = s.substr(i);
        st.insert(minCut(w)+minCut(left)+1);
     }
      return *st.begin();
 }
 bool isPalindrome(const string& s){
     return s == string(s.rbegin(), s.rend());
 }

可惜这样做法时间复杂度太高，无法通过。需要改写为非递归形式
2
定义f(i)为字符串[i, n-1]的最小cut数目 从左往右扫描，每找到一个回文就算作一次dp，于是新状态转移方程：f(i) = min{ f(j+1)+1} ,i<=j<len

int minCut(string s) {
        int len = s.size();
        //dp[i] 代表s.substr(i)的最小cut数目
        vector dp(len+1, 0);
        dp[len] = -1;
        for(int i=len-1; i >=0; --i){
            dp[i] = INT_MAX;
            for(int j=i+1; j<= len; ++j){
                if(isPalindrome(s.substr(i, j-i))){
                    dp[i] = min(dp[i], dp[j]+1);
                }
            }
        }
        return dp[0];
    }
    bool isPalindrome(const string& s){
        return s == string(s.rbegin(), s.rend());
    }

    bool check(string s){
        int left=0;
        int right=s.length()-1;
        while(left<=right){
            if(s[left]!=s[right])
                break;
            left++;
            right--;
        }
        return (left>right)?true:false;
    }

    int minCut(string s) {         int lens=s.length();
        vector<int> dp(lens+1,0);
        dp[lens]=-1;
        for(int i=lens-1;i>=0;i--){
            dp[i]=INT_MAX;
            for(int j=i;j<lens;j++){
                if(check(s.substr(i,j-i+1))){
                    dp[i]=std::min(dp[i],1+dp[j+1]);
                }
            }
        }
        return dp[0];
    }

int minCut(string s)
{
    int len = s.size();
    vector<vector<bool> > dp(len + 1,vector<bool>(len + 1,false));
    int f[len + 1];
    for(int i = 0; i <= len; i++)
        f[i] = len - i -1;
    for(int i = len - 1; i >= 0; i--)
    {
        for(int j = i; j < len; j++)
        {
            if(s[i] == s[j] && (j - i < 2  || dp[i + 1][j - 1]))
            {
                dp[i][j] = true;
                f[i] = min(f[i], f[j + 1] + 1);
            }
        }
    }
    return f[0];
}

/*
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s ="aab",
Return1since the palindrome partitioning["aa","b"]could be produced using 1 cut.

analysis:
定义状态数组: minCuts[n], minCuts[j]表示从0到j(包含j)的子串所需要用到的最小的切割次数
状态转移方程: 当子串str[i...j]是一个回文子串时, minCuts[j] = min(minCuts[i-1] + 1, minCuts[i])

注意的是: 

1. 此时如果i = 0, 则表示当前的str[0...j]不需要切割，即: minCuts[j] = 0;
2. 初始化和计算每一项之前都默认minCuts[j] = minCuts[j-1] + 1, 其中的原因自己分析吧;
3. 当检测到目前str[0...j]是回文的时候, 需要再一次把minCuts[j] = 0;

*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <map>

using namespace std;
class Solution {
public:
    int minCut(string s) {
        int* minCuts = new int[s.length()];
        int i, j, len;

        for(minCuts[0] = 0, i = 1, len = s.length(); i < len; ++i)
        {
			if(true == palindro(s, 0, i))
				minCuts[i] = 0;
			else
				minCuts[i] = minCuts[i-1] + 1;
        }
        
        for(j = 1; j < len; ++j) {
			
			minCuts[j] = minCuts[j-1] + 1;

			for(i = j-1; i >= 0; --i) {	

				if(true == palindro(s, i, j)) {
					if(i > 0) {
						if(minCuts[j] > minCuts[i-1] + 1)
							minCuts[j] = minCuts[i-1] + 1;
					} else {
						minCuts[j] = 0;
					}
				}
				
			}
        }
        
        len = minCuts[len - 1];
        delete minCuts;
        return len;
    }
	bool palindro(string &s, int left, int right)
	{
		int i, j;
		for(i = left, j = right; i < j; ++i, --j)
		{
			if(s[i] != s[j])
			return false;
		}
		return true;
	}
		
};

C++：

class Solution {
public:
    int minCut(string s) {
        int len = s.size();
        int D[len + 1];
        bool P[len][len];
        for (int i = 0; i <= len; ++i) {
            D[i] = len - i;
        }
        for (int i = 0; i < len; ++i) {
            for (int j = 0; j < len; ++j) {
                P[i][j] = false;
            }
        }
        for (int i = len - 1; i >= 0; --i) {
            for (int j = i; j < len; ++j) {
                if (s[i] == s[j] && (j - i < 2 || P[i + 1][j - 1])) {
                    P[i][j] = true;
                    D[i] = min(D[i], D[j + 1] + 1);
                }
            }
        }
        return D[0] - 1;
    }
};

class Solution {
public:
    int minCut(string s) {
        int len = s.length();
        int cnts[len]; // 保存每[0, N]子串的最小切割次数
        int ishw[len][len]; // 记录每个子串是否为回文串
        for (int i = 0; i < len; i++) {
            cnts[i] = 0;
            for (int j = 0; j < len; j++) {
                ishw[i][j] = i == j ? 1 : 0;
            }
        }
        
        for (int i = 1; i < len; i++) {
            int min_v = cnts[i-1] + 1;   // s[i]为回文，初始化最小切割次数
            for (int j = i - 1; j >= 0; j--) { // 当添加一个新的字符s[i]时，检测其是否与之前的连续字符构成回文串
                if (s[j] == s[i] && (i - j <= 1 || ishw[j+1][i-1])) { // 如果与之前的连续字符为回文串
                    ishw[j][i] = 1; // 更新记录
                    min_v = min(min_v, j == 0 ? 0 : cnts[j - 1] + 1); // 则最小切割次数为cnts[0, j-1] + 1或者是0
                }
            }
            cnts[i] = min_v; // 记录新添加一个字符后的最小切割次数
        }
        return cnts[len - 1];
    }
};

class Solution {
    public int minCut(String s) {
        
        /**
         *  使用动态规划寻找最优解，假设s(0,n)为字符串，s(0,i)为前i+1个字符的子串, f(i)为s(0,i)的最小分割次数
         *  问题分解为寻找一个整数j, j in [0,i], 使得s[i,j]是一个回文串，那么 f(i) = min(f(j)+1)
         *  寻找这样一个j使得f(i)最小即可, 得到状态转移方程
         *  初始赋值i=0, j=0 f(0) = 0
         *  边界值j=0, s[0,i]整个是一个回文串, f(i) = 0;
        **/
        
        // count[i] 记录 [0, i] 字符串的最小分割次数
        int[] count = new int[s.length()];
        
        // dp[j][i] 记录 [j, i] 字符串是否是回文串,已经比较过的没有必要再次比较
        boolean[][] dp = new boolean[s.length()][s.length()];
        
        for(int i=0; i<s.length(); i++){
            // 初始化,使用Integer.MAX_VALUE也可以,但是由题目可知最大也不过 字符串长度-1
            count[i] = i;
            for(int j=0; j<=i; j++){
                // 如果s[i]==s[j],那么s[j+1,i-1]如果是回文，那么s[j,i]就是回文
                if(s.charAt(j)==s.charAt(i)&&(i-j<3||dp[j+1][i-1])){
                    dp[j][i] = true;
                    // 边界值
                    if(j==0){
                        count[i] = 0;
                        continue;
                    }
                    // f(i) = min(f(j)+1)
                    count[i] = Math.min(count[i], count[j-1]+1);
                }
            }
        }
        return count[s.length()-1];
    }
}

public class Solution {
    public int minCut(String s) {
        int size = s.length();
        int [] dp = new int[size];
        boolean [][] isPalindrome = new boolean [size][size];
        for(int i = size - 1; i >= 0; i--){
            dp[i] = size - i;
            for(int j = i; j < size; j++){
                if(s.charAt(i) == s.charAt(j) && (j - i < 3 || isPalindrome[i + 1][j - 1])){
                    isPalindrome[i][j] = true;
                    if(j == size - 1){
                        dp[i] = 0;
                    }else if(dp[j + 1] + 1 < dp[i]){
                        dp[i] = dp[j + 1] + 1;
                    }
                }
            }
        }
        return dp[0];
    }
}

	class Solution {



	public:



	    int minCut(string s)



	    {



	        intlen = s.size();



	        vector<int> dp(len + 1);



	        for(inti = 0; i <= len; ++i)



	        {



	            dp[i] = i - 1;



	        }



	        for(inti = 0; i < len; ++i)



	        {



	            extend(s, i, i, dp);



	            extend(s, i, i + 1, dp);



	        }



	        return dp[len];



	    }



	    void extend(string &s, int i, int j, vector<int> &dp)



	    {



	        for(; i >= 0 && j < s.size(); --i, ++j)



	        {



	            if(s[i] != s[j])



	                break;



	            dp[j + 1] = min(dp[j + 1], dp[i] + 1);



	        }



	    }



	};

每次末尾加的第i个字符排法分两种
1、新加入的字符和之前的不构成回文，之前i-1的字符还是按照之前的排，
然后这时dp[i]=dp[i-1]+1;
2、新加入的字符和前面的字符构成回文，这时候找到构成回文的index，把index到i看成一个
不可分割的字符串或者把0到index看成一个字符串（前提是index到i是回文的
），这时dp[i]=dp[index]+1;
但是按照新的回文序列分割不一定就比之前的分割次数少，所以综合起来最后的
dp[i]=Math.min(dp[i-1],dp[index])+1;
这是自己推出来的，但是看大佬的解法比我的时间复杂度小很多，权当参考
import java.util.*;
public class Solution {
  public  int minCut(String s) {
      int n=s.length();
        int[] dp=new int[n+1];
        boolean[] is=new boolean[n+1];
        is[0]=true;
        dp[0]=-1;
        for(int i=1;i<=n;i++){
            String str=s.substring(0,i);
            if(ispalindrome(str))
            {
                dp[i]=0;
                is[i]=true;

            }
            else{
                int index=palindindex2(str,is);
                if(ispalindrome(str.substring(index)))
                    dp[i]=Math.min(dp[i-1],Math.min(dp[palindindex(str)],dp[index]))+1;
                else
                    dp[i]=Math.min(dp[i-1], dp[palindindex(str)])+1;
            }

        }
        return dp[n];
    }
    public int palindindex(String str){
        for(int i=0;i<str.length();i++){
            if(ispalindrome(str.substring(i))){
                return i;
            }
        }
        return str.length()-1;
    }
   public  int palindindex2(String str,boolean[] is){
        for(int i=str.length();i>0;i--){
            if(is[i]==true){
                return i;
            }
        }
        return 1;

    }
    
    public  boolean ispalindrome(String str){
        if(str.length()==1)
            return true;
       StringBuilder sb=new StringBuilder(str);
        if(str.equals(sb.reverse().toString()))
            return true;
        else
        return false;
    }
}

class Solution {
public:
    int minCut(string s) {
        if (IsPalindrome(s))
            return 0;
        for (int i = s.size()-1; i > 0; --i)
            if (IsPalindrome(s.substr(0, i)))
                return 1+minCut(s.substr(i));
    }
    
    bool IsPalindrome(const string s)
    {
        return s==string(s.rbegin(),s.rend());
    }
};