算法1(记忆化搜索)

class Solution {
private:
    static const int maxn = 30;
    int f[maxn][maxn][maxn+1];
    bool dfs(int a, int b, int len, string& s1, string& s2) {
        if(f[a][b][len] != -1) return f[a][b][len];
        if(len == 1) return s1[a] == s2[b];
        for(int i = 1; i < len; i++) {
            if(dfs(a,b,i,s1,s2) && dfs(a+i,b+i,len-i,s1,s2)) {
                f[a][b][len] = 1;
                return true;
            }
            if(dfs(a,b+len-i,i,s1,s2) && dfs(a+i,b,len-i,s1,s2)) {
                f[a][b][len] = 1;
                return true;
            }
        }
        f[a][b][len] = 0;
        return false;
    }
public:
    bool isScramble(string s1, string s2) {
        int n = s1.size();
        memset(f, -1, sizeof f);
        return dfs(0,0,n,s1,s2);
    }
};
// bool dfs(int a, int b, int len, string& s1, string& s2)

算法2(DP)

class Solution {
private:
    static const int maxn = 30;
    int f[maxn][maxn][maxn+1];
public:
    bool isScramble(string s1, string s2) {
        int n = s1.size();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) 
                f[i][j][1] = s1[i] == s2[j];
        }
        for(int len = 2; len <= n; len++) {
            for(int a = 0; a <= n - len; a++) {
                for(int b = 0; b <= n - len; b++) {
                    for(int i = 1; i < len && !f[a][b][len]; i++) {
                        f[a][b][len] |= f[a][b][i] & f[a+i][b+i][len-i];
                        f[a][b][len] |= f[a][b+len-i][i] & f[a+i][b][len-i];
                    }
                }
            }
        }
        return f[0][0][n];
    }
};
// bool dfs(int a, int b, int len, string& s1, string& s2)