leet_132

题目：

给定一个字符串S，问：字符串最少可以被划分成几个回文串

如:"ababaccdcca" => ["ababa", "ccdcc", "a"]

题解： 这道题是一个双重DP，因为字符串要被划分成多个子串，而每个子串都要是回文串，因此我们可以枚举最左边第一个回文串。设DP[i][j]表示把字符串S[i..j]划分成回文串最少需要的划分次数，假设S[0..i]是回文串，那么这种划分需要的次数就是 1 + dp[i+1][last]，所以，最小值就是min{1+dp[k][last]}(k∈[0,last])。 这其中还有个问题，就是如何判断S[0..i]是否是回文串，这个也可以DP解决。DP[i][j]表示S[i..j]是否是回文串，如果s[i] == s[j]那么 DP[i][j] = dp[i+1][j-1]。