DP on Grids and Strings
Fill a two-dimensional table where each cell depends on its neighbours - counting grid paths, longest common subsequence and edit distance.
The problem
Sometimes one index is not enough to describe a subproblem. A robot in a grid needs a row and a column. Two strings need a position in each. The state then has two numbers, so the table is 2D: dp[i][j].
The recipe does not change. Write the state, transition, base case and answer, then fill the table in an order where every cell's dependencies are already filled.
1 of 8