1 Palindrome Partitioning
问题来源：Palindrome Partitioning
该问题简单来说就是给定一个字符串，将字符串分成多个部分，满足每一部分都是回文串，请输出所有可能的情况。
该问题的难度比较大，很可能第一次遇到没有思路，这很正常。下面我们一点点分析，逐步理清思路。先不考虑所有的情况，针对一个符合条件的划分，每一部分都是一个回文子串，而且各部分的长度不固定。也即每一部分都是原始字符串的一个子串，且满足回文条件。所有的划分都满足上述条件，所以这就启发我们首先判断原始字符串的任意子串是否为回文子串。判断一个字符串是否为回文串最简单的方法是对字符串进行遍历。得到回文子串的结果之后我们该如何利用去获得所有可能的划分呢？此时，该问题就变为一个典型的深搜问题，问题的解空间就是所有可能划分的划分树，我们只需要遍历所有的分支直到叶节点，即为一个可能的划分。按照这个思路完成的代码如下：
public class Solution {public ArrayList<ArrayList<String>> partition(String s) {int[][] dp=new int[s.length()][s.length()];ArrayList<ArrayList<String>> result=new ArrayList<ArrayList<String>>();ArrayList<String> r=new ArrayList<String>();for(int i=0;i<s.length();i++){for(int j=i;j<s.length();j++){int k=0;for(;k<(j-i+1)/2;k++){if(s.charAt(i+k)!=s.charAt(j-k)) break;}if(k==(j-i+1)/2){dp[i][j]=1;}}}dfs(0,s,dp,r,result);return result;}void dfs(int i,String s,int[][] dp,ArrayList<String> r,ArrayList<ArrayList<String>> result){if(i==s.length()){ArrayList<String> t=new ArrayList<String>(r);Collections.reverse(t);result.add(t);return;}for(int j=i;j<s.length();j++){if(dp[i][j]==1){r.add(0,s.substring(i,j+1));dfs(j+1,s,dp,r,result);r.remove(0);}}}}
上述代码看似比较复杂，但其实就两个简单的部分：判断子串是否为回文串，然后深搜遍历所有的划分。判断子串是否为回文串采用了最朴素的循环遍历，在该题通过了测试，但是在第二题中将会超时，后面还会提到。深搜函数最重要的参数是第一个i，用来表示从字符串的i位置开始求划分，如果i已经超过了字符串的长度就说明完成了划分，保存一个可能的结果。如果i没有到字符串末尾，则判断从i开始到哪些位置是回文串，保存该回文串，然后从下一个位置继续深搜。如此就可以获得所有的划分。
2 Palindrome Partitioning II
问题来源：Palindrome Partitioning II
该问题是问题I的变种，现在不求所有的划分，而只求分组个数最小的划分。
2.1 深搜
该问题一开始的思路肯定是直接照搬问题I的方法，采用DFS去求解。如果我们按照这个思路去实现，提交的时候会发现算法超时，即使进行了一系列的调优也不行。下面是采用DFS的最原始代码：
void dfs(int i,int parts,int len,int[][] dp){if(i==len){if(parts<minParts){minParts=parts;}return;}for(int j=i;j<len;j++){if(dp[i][j]==1){dfs(j+1,parts+1,len,dp);}}}
代码是一个典型的深搜，符合深搜的基本框架，但是当输入字符串是“ababababababababababababcbabababababababababababa”，算法超时。实际上这个字符串还是很短的，超时说明算法复杂度太高，或者可能需要对解空间进行剪枝，这就启发我首先试试剪枝是否有效。最容易想到的剪枝策略是：如果当前的分割的个数已经大于当前最优解，则我们停止对该路径的深搜，需要的修改是对深搜的判断条件进行修改，修改之后为：
void dfs(int i,int parts,int len,int[][] dp){if(i==len){if(parts<minParts){minParts=parts;}return;}for(int j=i;j<len;j++){if(dp[i][j]==1&&parts<minParts){dfs(j+1,parts+1,len,dp);}}}
但是这样还是超时，当字符串为：“fifgbeajcacehiicccfecbfhhgfiiecdcjjffbghdidbhbdbfbfjccgbbdcjheccfbhafehieabbdfeigbiaggchaeghaijfbjhi”时，算法超时。
我还是不死心，感觉肯定是深搜的思路不对，导致对算法的剪枝力度不够，，通过修改应该是可以通过的。后来一想，问题要求最短的分割，我们肯定需要首先考虑最长的回文子串，而之前的遍历都是从最短的回文子串开始遍历，可能这个是导致剪枝能力差的原因。按照这个思路修改代码，只需要将遍历回文子串的顺序修改一下即可：
void dfs(int i,int parts,int len,int[][] dp){if(i==len){if(parts<minParts){minParts=parts;}return;}for(int j=len-1;j>=i;j–){if(dp[i][j]==1&&parts<minParts){dfs(j+1,parts+1,len,dp);}}}
代码与上面的不同是修改了for循环的遍历次序，先从最长的回文子串开始遍历。但是结果令人失望，还是超时！当字符串是：
“”时，算法超时。我还是不相信确实是深搜的原因，所以将代码拷贝到eclipse中运行，结果运行了半小时也没有得出结果。好吧，只能承认算法思路不对。
重新思考算法，DFS超时一般的原因都是由于递归过程中的重复子问题导致重复计算，最典型的例子是斐波那契数列的计算，递归和非递归算法的运行效率完全是两个概念，貌似这个问题和斐波那契数列问题类似。
重新审视上面的DFS代码，我们会发现变量只有前两个，后两个都是常量，这样深搜的过程中可能就会存在重复子问题。对字符串“ababa”运行算法I，可以得到该字符串的所有可能回文子串划分为：
a b a b a
a b aba
a bab a
aba b a
ababa
如果用(i,j)表示从位置i开始，当前已经有j个分割的情况，则运行最原始的深搜算法可以得到调用树：
可笑的小心谨慎，还有从来就不会安全的安全感。
