## Yet Another Unique Paths

put the strings onto the matrix

``````+---+---+---+---+---+---+---+
|   | * | a | a | b | c | c |
+---+---+---+---+---+---+---+
| * |   |   |   |   |   |   |
+---+---+---+---+---+---+---+
| d |   |   |   |   |   |   |
+---+---+---+---+---+---+---+
| b |   |   |   |   |   |   |
+---+---+---+---+---+---+---+
| b |   |   |   |   |   |   |
+---+---+---+---+---+---+---+
| c |   |   |   |   |   |   |
+---+---+---+---+---+---+---+
| a |   |   |   |   |   |   |
+---+---+---+---+---+---+---+
``````

Paths for `aadbbcbcac`, from top-left ot bottom-right. each step can choose to go to the grid on the right or the grid on the bottom.

• from `1,1` goto `1,2` use letter `a` in `aabcc`
• from `1,2` goto `1,3` use letter `a` in `aabcc`
• from `1,3` goto `2,3` use letter `d` in `dbbca`
• fork from `2,3`, the next step can be `2,4` or `3,3`
• ...
• until no next step or reach the bottom right grid.
``````+---+---+---+---+---+---+---+
|   | * | a | a | b | c | c |  0
+---+---+---+---+---+---+---+
| * | 1 | 1 | 1 |   |   |   |  1
+---+---+---+---+---+---+---+
| d |   |   | 1 | 1 |   |   |  2
+---+---+---+---+---+---+---+
| b |   |   | 2 | 1 | 1 |   |  3
+---+---+---+---+---+---+---+
| b |   |   | 2 |   | 1 |   |  4
+---+---+---+---+---+---+---+
| c |   |   | 2 | 2 |1 2|   |  5
+---+---+---+---+---+---+---+
| a |   |   |   |   |1 2|1 2|  6
+---+---+---+---+---+---+---+
0   1   2   3   4   5   6
``````

Paths for `aadbbbaccc`

``````+---+---+---+---+---+---+---+
|   | * | a | a | b | c | c |
+---+---+---+---+---+---+---+
| * | 1 | 1 | 1 |   |   |   |
+---+---+---+---+---+---+---+
| d |   |   | 1 | 1 |   |   |
+---+---+---+---+---+---+---+
| b |   |   | 2 | 1 |   |   |
+---+---+---+---+---+---+---+
| b |   |   | 2 | 1 |   |   |
+---+---+---+---+---+---+---+
| c |   |   |   |   |   |   |
+---+---+---+---+---+---+---+
| a |   |   |   |   |   |   |
+---+---+---+---+---+---+---+
``````

No path can reach the bottom right grid.

## Dynamic programming

`P[i][j]` indicates that there is an `Interleaving String` formed by `S1[0..i - 1]` and `S2[0..j - 1]`.

• `P[1][1]` = true
• `P[i][j] = (P[i - 1][j] || P[i][j - 1]) && (S3[i + j - 1] == S1[i - 1] || S3[i + j - 1] == S2[j - 1])`

I think Dynamic programming is brain fucking. Not as easy as the girds, but, essentially, they are the same.