DP II: grids, strings, intervals
A subproblem named by two positions: a square of a grid, a prefix of each of two strings, or the two ends of an interval. Draw the arrows from a cell to the cells it reads, and they tell you what order to fill the table in.
Problems worked on this page, and more to practise
- 1143. Longest Common Subsequence
- 72. Edit Distance
- 312. Burst Balloons
- 62. Unique Paths
- 63. Unique Paths II
- 64. Minimum Path Sum
- 221. Maximal Square
- 5. Longest Palindromic Substring
- 516. Longest Palindromic Subsequence
- 97. Interleaving String
- 1312. Minimum Insertion Steps to Make a String Palindrome
- 115. Distinct Subsequences
- 329. Longest Increasing Path in a Matrix
When does a dynamic programming table need two indices?
When one subproblem is named by two positions rather than one. A square of a grid is a row and a column. A pair of string prefixes is how much of each string you have used. An interval is its two ends. If you can write down the question a cell answers and it needs two numbers to say it, the table is two-dimensional. Everything else about the method is the same as the linear case.
Why is the DP table one row and one column bigger than the two strings?
Row 0 stands for the empty prefix of the first string and column 0 for the empty prefix of the second, and those are the base cases. A table of exactly n by m has nowhere to put them. The cost is one off-by-one that you have to get right every time: row i covers the first i characters, so the last of them is at index i - 1, and the comparison is s[i - 1] against t[j - 1].
What order should I fill a two-dimensional DP table in?
Whatever order makes every cell a recurrence reads already filled. Draw an arrow from a cell to each cell it reads and pick an order in which every arrow points backwards. Grid paths and the two-string problems read the row above and the cell to the left, so row by row, left to right, works. Interval DP reads shorter intervals inside the one being filled, so the order is by increasing length, and row order is wrong.
Can a two-dimensional DP be reduced to one row?
Yes, whenever a cell reads only its own row and the row above it. Keep one row and write over it in place. The catch is the diagonal: dp[i-1][j-1] is the value in the previous row at column j - 1, and by the time you reach column j you have already overwritten it. Save it in a variable before the write. The reduction gives up the traceback, so keep the full table if you need the answer itself and not just its size.
Why does Burst Balloons choose the last balloon to burst instead of the first?
Because the choice has to leave two independent subproblems. Burst a balloon first and the two halves become neighbours, so what each half is worth depends on the other. Burst it last and every other balloon in the interval is already gone, so its neighbours at that moment are the two balloons at the ends of the interval, which never move. The two sides are then separate intervals and the table already holds them.