这道题用DP来解决，也可以用递归，但是时间复杂度很高，被报TLE。

下面是DP的AC代码。

1 /** 2      * Solution 2 :DP Accepted 3      * create a (len1+1) x (len2+1) matrix A, A[i][j] means s3[0...i+j-1] is formed by the interleaving of s1[0...i-1] and s2[0...j-1] 4      * A[i][j] =  True   if A[i-1][j] = true && s3[i+j-1] = s1[i-1] or A[i][j-1] = true && s3[i+j-1] = s2[j-1]; 5      *            False  else 6      * @param s1 7      * @param s2 8      * @param s3 9      * @return10      */11     public boolean isInterleave2(String s1, String s2, String s3){12         int len1 = s1.length();13         int len2 = s2.length();14         int len3 = s3.length();15         16         if(len1+len2!=len3)17             return false;18         19         char[] c1 = s1.toCharArray();20         char[] c2 = s2.toCharArray();21         char[] c3 = s3.toCharArray();22         23         //DP24         boolean[][] A = new boolean[len1+1][len2+1];25         A[0][0] = true;26         for(int i = 1;i<=len1;i++)27             if( A[i-1][0]== true && c3[i-1] == c1[i-1])28                 A[i][0] = true;29             else30                 A[i][0] = false;31         for(int j=1;j<=len2;j++)32             if(A[0][j-1] == true && c3[j-1] == c2[j-1])33                 A[0][j] = true;34             else35                 A[0][j] = false;36         37         for(int i=1;i<=len1;i++){38             for(int j=1;j<=len2;j++){39                 if(A[i-1][j] == false && A[i][j-1] == false)40                     A[i][j] = false;41                 else if(A[i-1][j] == true && c3[i+j-1] == c1[i-1])42                     A[i][j] = true;43                 else if(A[i][j-1] == true && c3[i+j-1] == c2[j-1])44                     A[i][j] = true;45                 else46                     A[i][j] = false;47             }48         }49         return A[len1][len2];50     }