joshua分享：dp[i][j]定义：用s1[1...i],s2[1...j] 能否匹配 s3[1...i+j]

这道题比较简单，一开始写的递归，后来改成循环，发现都超时。
写了一个简易版本的dp，如下所示：
dp[i][j]定义：s1[1...i],s2[1...j]能否顺序匹配 s3[i+j]
状态转移方程：有两种状态：
1. dp[i][j] = dp[i-1][j], if dp[i-1][j] && s1[i] == s3[i+j]
** 表示s1的第i个字符匹配s3的第i+j个字符；**
2. dp[i][j] = dp[i][j-1], if dp[i][j-1] && s2[j] == s3[i+j]
** 表示s2的第j个字符匹配s3的第i+j个字符；**
上面两种情况，只要有一个结果为true，那么当前的匹配就为true

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int len1 = s1.size(),
            len2 = s2.size(),
            len3 = s3.size();

        if(len1+len2 != len3) return false;
        //把三个字符串均右移一个位置，从1开始索引，方便计算，哈哈！
        s1.insert(0, " ");
        s2.insert(0, " ");
        s3.insert(0, " ");
        // [1...len1][1...len2]为有效区间，
        vector<vector<bool> > dp(len1+1, vector<bool>(len2+1, false));
        // 首先分三步进行初始化
        dp[0][0] = true;
        for(int j = 1; j <= len2; j++) 
            if(s2[j] == s3[j]) dp[0][j] = dp[0][j-1];
        for(int i = 1; i <= len1; i++) 
            if(s1[i] == s3[i]) dp[i][0] = dp[i-1][0];

        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2; j++) {
                // 大佬们的回复都是直接用一个开关，我改成这一种if判断的情况，方便大家理解
                // 请勿喷，我喜欢看起来简单的东西
                if((dp[i-1][j] && s1[i] == s3[i+j]) || 
                   (dp[i][j-1] && s2[j] == s3[i+j])) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[len1][len2];
    }
};