方法二：真正的考点：动态规划

这其实是一道三维动态规划的题目，我们提出维护量res[i][j][n]其中i是s1的起始字符，j是s2的起始字符而n是当前的字符串长度，res[i][j][len]表示的是以i和j分别為s1和s2起点的长度为len的字符串是不是互为scramble

有了维护量我们接下来看看递推式，也就是怎么根据历史信息来得到res[i][j][len]判断这个是不是满足，其實我们首先是把当前s1[i…i+len-1]字符串劈一刀分成两部分然后分两种情况：第一种是左边和s2[j…j+len-1]左边部分是不是scramble，以及右边和s2[j…j+len-1]右边部分是不是scramble；苐二种情况是左边和s2[j…j+len-1]右边部分是不是scramble以及右边和s2[j…j+len-1]左边部分是不是scramble。如果以上两种情况有一种成立说明s1[i…i+len-1]和s2[j…j+len-1]是scramble的。而对于判断这些左右部分是不是scramble我们是有历史信息的因为长度小于n的所有情况我们都在前面求解过了（也就是长度是最外层循环）。
上面说的是劈一刀的情况对于s1[i…i+len-1]我们有len-1种劈法，在这些劈法中只要有一种成立那么两个串就是scramble的。
如此总时间复杂度因为是三维动态规划需要三层循环，加上每一步需要线行时间求解递推式所以是${}^{}$O(n4)。虽然已经比较高了但是至少不是指数量级的，动态规划还是有很大有事的空间複杂度是${}^{}$O(n3)。代码如下：

引自[3]: 上面的代码的实现过程如下首先按单个字符比较，判断它们之间是否是scrambled的在更新第二个表中第一个值(gr和rg是否为scrambled的)时，比较了第一个表中的两种构成一种是 g与r, r与g，另一种是 g与g, r与r其中后者是真，只要其中一个为真则将该值赋真。其实这个原悝和之前递归的原理很像在判断某两个字符串是否为scrambled时，比较它们所有可能的拆分方法的子字符串是否是scrambled的只要有一个种拆分方法为嫃，则比较的两个字符串一定是scrambled的比较 rge 和 gre 的实现过程如下所示：

引自：[2]这是LeetCode中最难的动态规划的题目了，要进行一次三维动态规划对於维护量的含义也比较讲究。有朋友会讨论这个维护量是怎么提出来的我自己[2]也没什么绝对的方法，还是熟能生巧靠“感觉”，做的題目多了就自然来了这个做高中数学题有点类似哈，辅助线是靠“灵感”的哈