97.InterleavingString.md

1. 如果画一个2d图, s1往下, s2往右, dp[i][j]表示s2的前i个字母和s1的前j个字母和s3的配对情况;
2. 而且因为dp[i][j]就对应两个string的前i和j个字母，判断s3的时候对应的index就是i+j-1.
3. 其实难得想的是，dp准备来表示什么;
4. bool类型的返回值的dp, 很多都是这种从左边和上边两边转移过来的状态转移方程。

C++:

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) return false;
        int n1 = s1.size(), n2 = s2.size();
        vector<vector<int>> dp(n1+1, vector<int>(n2+1, 0));
        dp[0][0] = true;
        for (int i = 1; i <= n1; ++i) {
            dp[i][0] = dp[i-1][0] && s1[i-1] == s3[i-1];
        }
        for (int j = 1; j <= n2; ++j) {
            dp[0][j] = dp[0][j-1] && s2[j-1] == s3[j-1];
        }
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                dp[i][j] = (dp[i-1][j] && s1[i-1] == s3[i+j-1]) || (dp[i][j-1] && s2[j-1] == s3[i+j-1]);
            }
        }
        return dp[n1][n2];
    }
};