思路分析
首先，这是个三维DP，不要上来傻乎乎敲朴素搜索，标记为Hard的题目自然是有一定难度的。如果是Onsite遇到这类问题，思路明显错误的话，我想面试官应该会给出一定的提示。
回到正题。先考虑怎样记录状态，对于这个问题，显然应该有dp[i][j][k]表示s1.substr(i, k)与s2.substr(j, k)能否构成“Scramble String”，而答案应该就是dp[0][0][length]。还是使用传统的左闭右开区间可以使得问题的表述非常清晰，于是接下来考虑如何进行状态转移。
如果DP思路清晰的话，可以直接写出一个四重循环递推。优点是一眼就能看出复杂度为O(n^4)，而缺点则是不大好想，对于DP没有经验的话边界细节、递推顺序很容易弄错。对于我这样的DP渣渣，就直接上记忆化搜索的写法了，优点是优雅好写，但是复杂度常数就要大很多。但是总而言之，一切DP都可以用记忆化搜索来表达。
记忆化搜索的思想是，对于任何一个被搜索的状态DFS(i,j,len)，枚举一个切分位置k，只要满足DFS(i,j,k)&&DFS(i+k,j+k,len-k)||DFS(i,j+len-k,k)&&DFS(i+k,j,len-k)为真，那么该状态就是为真的。这个表达式的意思是，我们将s1中从i起始长度为len的字符串从k处切分成长度为k和len-k的两段，对s2也做同样的操作，如果存在“前前后后”或者“前后后前”的匹配方式，则说明可以构成“Scramble String”，否则就不可以。仔细观察字符串的构造方式，就可以发现这个表达式的含义是显然的。
代码
#define REP(i,a,b) for(int i=a;i