97. Interleaving String
给你三个字串 s1,s2,s3 ，求出是否可以透过交替的插入s1和s2的字符来得到s3。
Example 1:
https://assets.leetcode.com/uploads/2020/09/02/interleave.jpg
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: One way to obtain s3 is:
Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a".
Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" =
"aadbbcbcac".
Since s3 can be obtained by interleaving s1 and s2, we return true.
Example 2:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Explanation: Notice how it is impossible to interleave s2 with any other
string to obtain s3.
Example 3:
Input: s1 = "", s2 = "", s3 = ""
Output: true
思路：
1.选或不选大多都是动态规划问题，先找几个简单的case画一张表格就可以看出
递移的方程式了。
2.首先排除明显不符合的 case，若 s1 和 s2 相加长度不等于 s3 可以直接返回 false。
3.定义dp[i][j] 表示用了 i 个 s1 字符、j 个 s2 的字符组出来的字串是否等于
s3[0,i+j]，要得到当前的 dp[i][j] 只可能有两种方式组合：
> 用了 i-1 个 s1，j 个 s1 字符，并使用了第 i 个 s1 字符
> 用了 i 个 s1，j -1 个 s2 字符，并使用了第 j 个 s2 字符
如果前一轮组的字串等于 s3 的子字串且当前拿的字串也等于 s3 的下个字串当前就为
true，只要其中一种拿法为真即可（ab 和 ba 不重要）。
4.因为要取前一个所以要初始化第一行和第一列，base case dp[0][0] 为 true，跑完
动态规划返回 dp[n][m] 即可。
Java Code：