LeetCode | Palindrome Partitioning II

题目描述：

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.

Example:
Input: “aab”
Output: 1

Explanation: The palindrome partitioning [“aa”,”b”] could be produced using 1 cut.

---

Solution：

使用动态规划，求最优解朝着动态规划这个方向想。

  public int minCut(String s) {
  	int n = s.length();
      boolean  dp[][] = new boolean[n][n];//判断是否是回文串
      int cut[] = new int[n];//存储最小cut值
      int min;
      for (int i = 0; i < n; i++) {//i是substring的尾部
      	min = i;
	for (int j = 0; j <= i ; j++) {//j是substring的头部
		//j+1 > i-1表示对角线部分，也就是一个字符作为一个回文串substring
		if (s.charAt(i) == s.charAt(j) && (j+1 > i-1 || dp[j+1][i-1])) {
			dp[j][i] = true;
			if(j == 0)//表示尾部第i个和头部第一个字符相同，而且中间也是回文串，也就是这个串就是一个回文串，所以cut值直接就是0
				min = 0;
			else 
				//此时表示s.substring(j,i+1)是个回文串，也就是s[j]~s[i]之间的字符构成一个回文串
				//注意关键在这个cut[j-1]而不是cut[i-1],
				//cut[j-1]表示是s[j-1]之前的最小的cut值，
				//此时是s[j]~s[i]是一个回文串，所以cut[i]之间从cut[j-1]加1即可
				min = Math.min(min, cut[j-1]+1);
		}
	}
	cut[i] = min;
}
      return cut[n-1];
  }