LeetCode刷题：132. Palindrome Partitioning II
原题链接：https://leetcode.com/problems/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.
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的最少分割次数。
示例:
输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
算法设计
/** 基本思想是使用两个DP数组：* 使用isPalindrome[i，j]来记录 s[i, j]是否为回文串，* 以及num[i]来记录对于s[0，i]的最小划分。* 这里s[i，j]代表的含义是：s.substring（i，j+1）。* 遍历访问数组以计算：num 和 ispalindrome。* num[s.length（）-1]是我们想要的结果。* 注意，如果s[0，i]是回文串，那么num[i]等于零，因为我们不需要划分它来得到回文序列。* */public int minCut(String s) {char str[] = s.toCharArray();boolean isPalindrome[][] = new boolean[s.length()][s.length()];int num[] = new int[s.length()];for(int i = 0; i < s.length(); i++) {int min = Integer.MAX_VALUE;for(int j = 0; j <= i; j++) {if( str[i] == str[j] && (j + 1 >= i || isPalindrome[j + 1][i - 1]) ){isPalindrome[j][i] = true;min = j == 0 ? 0 : Math.min(min, num[j - 1] + 1);}}num[i] = min;}return num[s.length() - 1];}Accepted~
