DP — Interleaving String

solve(s1, s2, s3) — return true if s3 can be formed by interleaving s1
and s2: both strings are split into pieces and merged alternately, and the
relative order of the characters inside each string is preserved.

Let dp[i][j] mean "the first i characters of s1 and the first j of s2
can form the first i + j characters of s3". The next character of s3 must
come from s1 or from s2.

Examples

solve("aabcc", "dbbca", "aadbbcbcac")  → true
solve("aabcc", "dbbca", "aadbbbaccc")  → false
solve("", "", "")                      → true
solve("a", "b", "ba")                  → true