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.

很明显要用动态规划解，注意s1跟s2的长度一定是相等的。

问题类似于钢条切割；只不过把钢条最大收益变成了是否是scrambled string

要记录s1中的某一段与s2中的某一段是否满足scrambled string条件，需要分别记录两段的起点于中点，但是，如果个子串满足条件，那么他们的长度必然是一样的。

所以备忘录的结构为三维数组，即子串1的起点i，子串2的起点j，以及串长k。即bool dp[i][j][k]

dp[i][j][k]  =  (dp[i][j][x] && dp[i + x][j + x][k - x]) || (dp[i][j + k - x][x] && dp[i + x][j][k - x])

k = 1的情况即边界情况

代码：

class Solution {public:    bool isScramble(string s1, string s2) {        int length = s1.length();          bool f[length][length][length];          memset(f, false, sizeof(bool) * length * length * length);                    for (int k = 1; k <= length; k++) {              for (int i = 0; i <= length - k; i++) {                  for (int j = 0; j <= length - k; j++) {                      if (k == 1) {                          f[i][j][k] = s1[i] == s2[j];                      }                      else {                          for (int l = 1; l < k; l++) {                              if ((f[i][j][l] && f[i + l][j + l][k - l]) || (f[i][j + k - l][l] && f[i + l][j][k - l])) {                                  f[i][j][k] = true;                                  break;                              }                                                      }                      }                  }              }                      }                            return f[0][0][length];      }  };

leetcode : Scramble String