[LeetCode]切割字符串，使各个子串都是回文
题目：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",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
思路：
用数组dp[i]表示从下标i开始的字符串分割为回文子串的最少个数，
paliin[i][j] 表示从下标i到下标j是否为回文串，
利用动态规划
dp[i] = min(dp[i], 1 + dp[j]) if (palin[i + 1][j - 1] == ture or j - i < 2 ) && s[i] = s[j] , i <= j < len ,
i从len - 1递减至0
总的时间复杂度为O(n^2)
code
1 class Solution { 2 public: 3 int minCut(string s) { 4 // Start typing your C/C++ solution below 5 // DO NOT write int main() function 6 int len = s.size(); 7 int dp[len + 1];//记录从i开始的最短切割次数 8 bool palin[len][len];//记录palin(i,j)是否为回文 9 //初始化dp[i] 10 for(int i = 0; i <= len; ++i) 11 dp[i] = len - i; 12 //初始化palin[i][j] 13 for(int i = 0; i < len; ++i) 14 for(int j = 0; j < len; ++j) 15 palin[i][j] = false; 16 //从后往前计算dp[i], 17 for(int i = len - 1; i >= 0; --i) 18 for(int j = i; j < len; ++j) 19 { 20 if(s[i] == s[j] && (j - i < 2 || palin[i + 1][j - 1])) 21 { 22 palin[i][j] = true; 23 dp[i] = min(dp[i], dp[j + 1] + 1); 24 } 25 } 26 return dp[0] - 1; 27 } 28 };