Scramble String

   dp[i][j][l] means whether s2.substr(j,l) is a scrambled string of s1.substr(i,l) or not.

 bool isScramble(string s1, string s2) {
        int len=s1.size();
        bool dp[len][len][len];
        for (int i=len-1;i>=0;i--)
            for (int j=len-1;j>=0;j--) {
                dp[i][j][1]=(s1[i]==s2[j]);
                for (int l=2;i+l<=len && j+l<=len;l++) {
                    dp[i][j][l]=false;
                    for (int n=1;n<l;n++) {
                        if(dp[i][j][n]&&dp[i+n][j+n][l-n]||dp[i][j+l-n][n]&&dp[i+n][j][l-n]){
                            dp[i][j][l]=true;
                            break;
                        }
                    }
                }
            }
        return dp[0][0][len];
    }

//another flavor
//DP. f(i, j, n) is true iff substring starts at s1[i] and substring starts at s2[j] both with length n+1 are scrambled
    bool isScramble(string s1, string s2) {
        int n = s1.size();
        if (s2.size() != n) return false;

        bool f[n][n][n];

        for (int i=0; i<n; i++)
            for (int j=0; j<n; j++)
                f[i][j][0] = s1[i] == s2[j];

        for (int l=1; l<n; l++) {
            for (int i=0; i+l<n; i++) {
                for (int j=0; j+l<n; j++) {
                    f[i][j][l] = false;
                    for (int k=0; k<l; k++) {
                        if (f[i][j][k] && f[i+k+1][j+k+1][l-1-k]
                            || f[i][j+l-k][k] && f[i+k+1][j][l-1-k]) {
                            f[i][j][l] = true;
                            break;
                        }
                    }
                }
            }
        }

        return f[0][0][n-1];
    }