Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
great / \ gr eat / \ / \g r e at / \ a t
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".
rgeat / \ rg eat / \ / \r g e at / \ a t
We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".
rgtae / \ rg tae / \ / \r g ta e / \ t a
We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
据说这是区间型dp的终极版本，其实难点在于如何定义状态，状态定义好了不难．首先这也是双序列问题，状态中肯定包括第一个序列的第ｉ个，第二个序列的第j个，但是仅仅用这个不够，我们需要加上第三维即长度，最终的转换状态是dp[x][y][k]，即第一个序列的x位开始，长度为k的序列和第二个序列的y位开始，长度为k的序列，是否是scramble string.
状态转换，显然像rgtae一样，我们需要找一个分割的位置，使得s2[y:y+k-1]按位置分割的这两段分别对应s1[x:x+k-1]中的两段：一共有两种对应关系，一种左边对应左边，右边对应右边，另外一种是左边对应右边，右边对应左边.如tae对应eat,或者eat对应eat.请看示意图：
初始化，可以先检查每个字符是否对应，即dp[x][y][1]．
最终结果是dp[0][0][n]．代码如下：
class Solution(object): def isScramble(self, s1, s2): """ :type s1: str :type s2: str :rtype: bool """ if len(s1) != len(s2): return False n = len(s1) dp = [[[False]*(n+1) for i in xrange(n)] for j in xrange(n)] for x in xrange(n): for y in xrange(n): if s1[x] == s2[y]: dp[x][y][1] = True for k in xrange(2, n+1): for x in xrange(0, n-k+1): for y in xrange(0, n-k+1): for i in xrange(1, k): if (dp[x][y][i] and dp[x+i][y+i][k-i]) or (dp[x][y+k-i][i] and dp[x+i][y][k-i]): dp[x][y][k] = True break return dp[0][0][n]
空间复杂度为Ｏ(n^3),时间复杂度为Ｏ(n^4).
这题如果不采用动态规划而是暴力递归解法．则需要枚举s1开始结束位置，s2开始结束位置，枚举s1和s2的切分位，所以复杂度为Ｏ(n^6).但是可以采取剪枝等优化方法．
有两种加速策略，一种是剪枝，提前返回；一种是加缓存，缓存中间结果，即 memorization（翻译为记忆化搜索）。具体参见leetcode-cpp题解．