【二维动态规划：交错字符串】-s1的[0…i-1]区间， s2的[0…j-1]区间， 能否组成s3[0…i+j-1]的区间。

1. 如果s1[i-1]==s3[i+j-1], 那么结果依赖dp[i-1][j]。
2. 如果s2[j-1]==s3[i+j-1], 那么结果依赖dp[i][j-1]。
3. 如果都不满足， 那么false, 不能交错组成。1，2情况任意一项成立， 那么结果为true。

dp表的简单部分如何填？
思考dp表的定义。
dp[0][0] = = true, 显然。 根据前面的定义， 取字符数组s1的0个， 另取字符数组的0个， 能否组成s3数组的0个。必然可以。

//单独取一个字符数组进行匹配s3前面几个字符
   	   for(int i=1;i<=n;i++){
           if(s1[i-1] != s3[i-1]){
               break;
           }
           dp[i][0] = true;
       }
       for(int j=1;j<=m;j++){
           if(s2[j-1] != s3[j-1]){
               break;
           }
           dp[0][j] = true;
       }

class Solution {
    public boolean isInterleave(String str1, String str2, String str3) {
        if(str1.length() + str2.length() != str3.length() ){
            return false;
        }
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();
        char[] s3 = str3.toCharArray();
        
        int n = s1.length;
        int m = s2.length;
        boolean[][] dp = new boolean[n+1][m+1];
        dp[0][0] = true;
        for(int i=1;i<=n;i++){
            if(s1[i-1] != s3[i-1]){
                break;
            }
            dp[i][0] = true;
        }
        for(int j=1;j<=m;j++){
            if(s2[j-1] != s3[j-1]){
                break;
            }
            dp[0][j] = true;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                dp[i][j] = (s1[i-1]==s3[i+j-1]&&dp[i-1][j])
                ||
                (s2[j-1]==s3[i+j-1]&&dp[i][j-1]);
            }
        }
        return dp[n][m];
    }
}

---

方法3：空间压缩+位置依赖

由于每一行都跟上一行的状态有关， 因此仅需一个一维数组和少数变量就可以滚动更新， 减少内存使用。

从第0行开始自上向下自左向右进行滚动， 压缩成一维dp表。

class Solution {
    public boolean isInterleave(String str1, String str2, String str3) {
        if (str1.length() + str2.length() != str3.length()) {
            return false;
        }

        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();
        char[] s3 = str3.toCharArray();

        int n = s1.length;
        int m = s2.length;

        boolean[] dp = new boolean[m + 1];
        
        // 初始化第一列的状态，表示 s1 完全匹配 s3 的情况
        dp[0] = true;
        for (int j = 1; j <= m; j++) {
            if (s2[j - 1] != s3[j - 1]) {
                break; // 如果 s2[j-1] 和 s3[j-1] 不相等，后续就不需要继续检查了
            }
            dp[j] = true; // 初始化 dp[j] 的状态
        }

        // 处理 s1 和 s2 的交错匹配
        for (int i = 1; i <= n; i++) {
            dp[0] = (s1[i - 1] == s3[i - 1]) && dp[0];  // 更新 dp[0] 状态
            for (int j = 1; j <= m; j++) {
                dp[j] = (s1[i - 1] == s3[i + j - 1] && dp[j]) || 
                        (s2[j - 1] == s3[i + j - 1] && dp[j - 1]);
            }
        }
        
        return dp[m];
    }
}

结语

动态规划的题解好难写…????????????.
空间压缩不会二维dp表真不好分析。