首页 > 代码库 > [Leetcode] Palindrome Partitioning II
[Leetcode] Palindrome Partitioning II
这是LeetCode上的一道题目，求出对于一个string，至少切多少刀可以让所有的substring都是回文串。原题是 https://oj.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.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
从题目看这是一个典型的动态规划题。我看到这题目立刻思维定势到算法书上教的矩阵连乘所需最少乘法数的问题。如果定义 dp[i][j]表示区间[i,j] 之间最小的cut 数，那么其递推关系可以写成
dp[i][j] = min( dp[i][k] + dp[k+1][j] + 1), i <= k < j。代码很容易就写出来了。
class Solution {public: int minCut(string s) { if(s.length()==0 || isPalindr(s)) return 0; const int N = s.length(); int cuts[N][N]; for(int k = 1; k <= N; k++){ for(int i = 0; i + k - 1 < N; i++){ if( s[i]==s[i+k-1] && (k <= 2 || cuts[i+1][i+k-2]==0) ) cuts[i][i+k-1] = 0; else{ cuts[i][i+k-1] = INT_MAX; for(int j = i; j < i+k-1; j++){ if(cuts[i][i+k-1] > cuts[i][j] + cuts[j+1][i+k-1] + 1) cuts[i][i+k-1] = cuts[i][j] + cuts[j+1][i+k-1] + 1; } } } } return cuts[0][N-1]; } bool isPalindr(string &s){ if(s.length()==0) return true; int left = 0, right = s.length() - 1; while(left <= right){ if(s[left++]!=s[right--]) return false; } return true; }};
这是一个O(n^3）的算法，而且内存消耗是O(n^2)，我提交的时候内存分配出问题了，那么什么地方可以做优化呢？
上面这个递推关系实际上把i, j中的所有位置的分割都尝试过去，如果 [k+1, j]不是回文串，则继续分割[k+1, j]直至其所有子串都是回文串，但是我们知道这样的分割必定在某个k‘ > k时被尝试过，所以在k处没有必要继续往下搜索，所以当[k+1, j]不是回文串时直接跳过就可以了。根据这个想法，就可以构造出一个一维的动态规划，用 f[i] 表示从第i位到第n-1位所需要的最少的切割数。先将f[i]初始化为f[i] = n-1-i。将i 从n-1到0循环，在每次循环内部，对i~n-1内的字符串进行扫描，每找到一个回文子串则更新一次数组，这时候的递推关系是 f[i] = min(f[i], f[j+1]+1)，需保证[i, j]为回文子串。
class Solution {public: int minCut(string s) { if(s.length()==0) return 0; const int N = s.length(); int cuts[N+1]; bool p[N][N]; fill_n(&p[0][0], N*N, false); for(int i = 0; i <= N; i++){ cuts[i] = N - i - 1; } for(int i = N-1; i >=0; i--){ for(int j = i; j < N; j++){ if(s[i]==s[j] && (j - i < 2 || p[i+1][j-1])){ p[i][j] = true; cuts[i] = min(cuts[i], cuts[j+1] + 1); } } } return cuts[0]; } int min(int a, int b){ return (a < b) ? a : b; }};
note:
1. 很多问题都有dp[i][j] = min( dp[i][k] + dp[k+1][j] + 1), i <= k < j 形式的递推关系，但是有些可以继续优化为O(n^2)，有些不能。关键问题在于这些最优的划分是否是重复的。
对于本题来说，最优划分有可能是重复的。例如字符串 s = "aabbbccb"，对于k=1, s将被拆分为 s1= "aa", s2 = "bbbccb"，而s2又会被继续拆分为"bb"和"bccb"，最终拆分结果是"aa", "bb"和"bccb"。对于k=3, s将被拆分为"aabb"和"bccb"，最终拆分结果仍然是"aa", "bb"和"bccb"。因此在k=1时继续拆分s2是不必要的，因为这样拆分的结果必定在其他地方已经被考虑了。用类似的思路可以处理 HDOJ上的一道题 http://acm.hdu.edu.cn/showproblem.php?pid=1227，在这道题里头最终的最优分配肯定满足对于某个i，i~n-1的餐馆由同一个仓库来供应。
对于另外一些问题，最优拆分可能不重复，例如多个矩阵相乘所需要的最少的乘法数。不同拆分最终对应不同的计算过程，这样的问题就不能用上面的思路进行优化了。
2. 优化的突破口是减少不必要的计算，不同的问题可能有不同形式的冗余计算。需要多思考多练习才能熟悉。
[Leetcode] Palindrome Partitioning II