Palindrome partition I II
这道题目引发出自己一直以来的一个思考，什么时候是二维DP，什么时候一维DP。
清晰记得如果一维DP足以表示状态，优先一维DP，这是算导的说法。
例如word break 一开始自己写二维DP，受了入门矩阵连的清晰，只要是区间DP，都是二维的，但是其实一维足以。
石子合并当时和谢老师讨论的时候，他说一维DP，我说会漏状态，所以还是二维DP比较合适。
现在回到这个palindrom partition问题来了，I 如果用一维DP完全可以，但是里面需要自己学一个isPalindrome函数，复杂度小算了一下，
sigma (i=1->n) sigma(j=0->i) (i-j) =1/2(1/6 n(n+1)*(2n+1) + n(n+1)/2) =O(n^3)
是三方的，虽然A了，但是因为这题需要返回结果，后面dfs，最坏是2^n个解，所以包容了这个复杂度，但是如果只是判定问题，例如
判定一个串是否可以partition palindrome的话，增加空间可以降低时间到平方的。例如这里的dp[i][j], 表示s(i…j) 是否可以划分回文串集合。
一维的dp[i]:似乎i作为长度更好，因为dp[0]是空的，但是注意 dp[i]往往和s[i-1] 关联如果作为索引考虑的东西会更多，例如单独处理dp[0], 看到小胖几乎都是这样的。
如果移步到II，会发现我之前的dp[] 超时了，在一个1500长度的串，三方不能忍了，因此开空间降复杂度，一般来说时间更重要，因此以后尽量开大状态。
G[] 要注意初始化为i-1, 然后特判j=0的情况
G[i]表示长度为i前缀的mincut次数，后面只需要看是否是回文就可以了，但是j=0 前面空串，后面整个串的情况要特殊处理一下。
一下是II的代码，是n^2的，因为没有判回文的函数，裸地两重循环
class Solution {
public:
bool dp[1500][1500];
int G[10000];
bool isPa(string s)
{
int n=s.size();
for(int i =0, j=n-1;i<j;i++, j--)
if(s[i]!=s[j]) return 0;
return 1;
}
int minCut(string s)
{
int n=s.size();
for(int i=0;i<n;i++) dp[i][i]=1;
for(int i=0;i<n-1;i++) dp[i][i+1]=s[i]==s[i+1];
for(int len=3;len<=n;len++)
{
for(int i=0;i<n;i++)
{
int j=i+len-1;
if(j>=n) continue;
dp[i][j]= dp[i+1][j-1] && s[i]==s[j];
}
}
G[0]=0;
for(int i=1;i<=n;i++)
{
G[i]=i-1;
for(int j=0;j<i;j++)
{
if(dp[j][i-1])
G[i]=min(G[i],j>0 ? G[j]+1 : 0);
}
}
return G[n];
}
};
以下是I的代码，三方的DP循环，后面DFS，所以很多书上说n^2 n^3严格都不对，因为要返回所有解，最坏指数个呢
class Solution {
public:
vector<string> cur;
vector< vector<string> > ans;
bool dp[10000];
int n;
string s_;
bool isPa(string s)
{
int n=s.size();
for(int i=0, j=n-1; i<j;i++, j--)
if(s[i]!=s[j]) return 0;
return 1;
}
vector<vector<string>> partition(string s) {
n=s.size();s_=s;
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<i;j++)
{
if(dp[j] && isPa(s.substr(j, i-j)))
{
dp[i]=1;
break;
}
}
}
ans.clear();cur.clear();
dfs(n);
return ans;
}
void dfs(int i)
{
if(i<=0)
{
ans.push_back(cur);
reverse(ans.back().begin(), ans.back().end());
}
else
{
for(int j=0;j<i;j++)
{
if(dp[j] && isPa(s_.substr(j, i-j)))
{
cur.push_back(s_.substr(j, i-j));
dfs(j);
cur.pop_back();
}
}
}
}
};
两方的算法，状态增加一维
class Solution {
public:
bool dp[1500][1500];
vector<string> cur;
vector<vector<string> > ans;
string s_;
vector<vector<string>> partition(string s) {
int n=s.size();s_=s;
for(int i=0;i<n;i++) dp[i][i]=1;
for(int i=0;i<n-1;i++) dp[i][i+1]=s[i]==s[i+1];
for(int len=3;len<=n;len++)
{
for(int i=0;i<n;i++)
{
int j=i+len-1;
if(j>=n) continue;
dp[i][j]=dp[i+1][j-1] && s[i]==s[j];
}
}
cur.clear();ans.clear();
dfs(0,n-1);
return ans;
}
void dfs(int s, int e)
{
if(s>e) ans.push_back(cur);
for(int i=s;i<=e;i++)
{
if( dp[s][i] )
{
cur.push_back(s_.substr(s,i-s+1));
dfs(i+1, e);
cur.pop_back();
}
}
}
};