Chapter 10: Dynamic Programming Basics

Every DP starts by choosing what one table entry means. Here $dp[i]$ is the number of distinct move sequences that end exactly on step $i$. To find a recurrence, split those sequences by their last move: a final 1-step comes from step $i - 1$ and a final 2-step comes from step $i - 2$. The groups are disjoint and cover every sequence, so $dp[i] = dp[i-1] + dp[i-2]$. Base cases stop the recursion: $dp[0] = 1$ counts the empty sequence, and $dp[1] = 1$. A wrong base case, such as $dp[0] = 0$, shifts or zeroes the whole table even when the recurrence is right.

Many one-dimensional problems share this shape: the current answer depends on a fixed number of earlier answers. When the allowed moves form a set $S$ of step sizes, splitting by the last move gives $dp[i] = \sum_{s \in S,\, s \le i} dp[i - s]$, with $dp[0] = 1$. For $S = \{1, 2\}$ this is Fibonacci, and for $S = \{1, 2, 3\}$ it is the Tribonacci sequence. Because each entry reads only the last $\max S$ entries, keeping those values in a few variables cuts memory from $O(n)$ to $O(1)$. The pattern breaks if order does not matter, as in counting coin combinations, where 1+2 and 2+1 must count once.

Define $dp[i]$ as the most money obtainable from houses $0$ through $i$, where $a_i$ is the cash in house $i$. Every valid plan either skips house $i$ or robs it. Skipping leaves the best plan for houses $0$ to $i-1$, which is $dp[i-1]$. Robbing forbids house $i-1$, so it adds $a_i$ to $dp[i-2]$. Hence $dp[i] = \max(dp[i-1], dp[i-2] + a_i)$, with $dp[0] = a_0$ and $dp[1] = \max(a_0, a_1)$. The constraint lives in the index $i - 2$: reading $dp[i-1]$ for the rob case could include house $i-1$ and break the rule. Only two earlier values matter, so two variables suffice.

House Robber is one instance of a pattern that recurs throughout DP: walk the items in order and, for each one, either include it, paying whatever constraint that imposes on earlier choices, or exclude it at no cost. The recurrence is the better of the two branches. The same skeleton solves 0/1 knapsack, where including an item uses capacity, and weighted interval scheduling, where including an interval rules out the ones it overlaps. When a constraint wraps around, as with houses on a circle, split the problem into cases that each become linear. If the constraint depends on more history, add a state dimension that records it.

Extending DP to a grid means the state needs two coordinates. Let $dp[i][j]$ be the minimum cost to reach cell $(i, j)$ from $(0, 0)$, including both endpoint costs, where grid[i][j] is the cost of a cell. With only right and down moves, the last step into $(i, j)$ comes from above or from the left, so $dp[i][j] = grid[i][j] + \min(dp[i-1][j], dp[i][j-1])$. The first row has no cell above and the first column has no cell to the left, so each is a running sum along its edge. Forgetting these boundaries makes code read index $-1$, which in Python silently wraps around to the last row or column.

A recurrence is only useful if every value it reads already exists. Draw an arrow from each cell to the cells it depends on: these arrows must form a DAG, and the loops must visit cells in a topological order of it. When $dp[i][j]$ reads $dp[i-1][j]$ and $dp[i][j-1]$, row-major order, top to bottom and left to right, works, and so does column-major order. The direction of the state can also be reversed: define the cost from $(i, j)$ to the goal and fill from the bottom-right corner. If a cell is read before it is written, the code does not crash; it silently uses the default value, usually zero.

To count routes rather than optimise them, let $dp[i][j]$ be the number of distinct right-and-down paths from $(0, 0)$ to $(i, j)$. The final move into $(i, j)$ comes from above or from the left, the two groups share no path, and together they cover every path, so $dp[i][j] = dp[i-1][j] + dp[i][j-1]$. Every cell in the first row or first column has exactly one path, a straight line, so those entries are 1. The table is Pascal's triangle turned on its side, which explains the closed form $\binom{m+n-2}{m-1}$. Counts grow quickly, so fixed-width languages need 64-bit integers or a modulus.

Blocked cells break the symmetry that the binomial formula relies on, but the DP barely changes. A blocked cell has no paths into it, so set $dp[i][j] = 0$ there; every other cell keeps $dp[i][j] = dp[i-1][j] + dp[i][j-1]$, and a zero neighbour simply contributes nothing. The subtle case is the edges. The first row is no longer all 1s: once an obstacle appears in it, every cell to its right is unreachable, and the same holds down the first column. If the start or goal is blocked, the answer is 0. Initialising the edges to 1 before applying obstacles is the most common bug.

Let $dp[i][j]$ be the smallest total of cell values on any right-and-down path from $(0, 0)$ to $(i, j)$, counting both ends, where grid[i][j] is the value in that cell. The last move comes from above or from the left, and whichever path reaches that neighbour, the best continuation from there is the same, which is optimal substructure. So $dp[i][j] = grid[i][j] + \min(dp[i-1][j], dp[i][j-1])$, with running sums along the first row and column. Viewed as a graph, the grid is a DAG, and row-major order is a topological order, so each cell is final once computed. This is why negative values, which break Dijkstra, cause no trouble here.

The full table uses $O(mn)$ memory, but each cell reads only the cell above and the cell to its left, so less is needed. One option writes each $dp[i][j]$ over grid[i][j]: when a cell is processed, its upper and left neighbours already hold finished DP values, and extra space drops to $O(1)$. The cost is that the input is destroyed, which breaks callers that reuse the grid. A safer option keeps a single row of length $n$: before the update, row[j] holds the value from the row above, and row[j-1] already holds the current row's left value. That uses $O(n)$ space and leaves the input unchanged.

The state does not have to be a cost or a count. Here $dp[i][j]$ is the side length of the largest square of 1s whose bottom-right corner is exactly at $(i, j)$. Anchoring at one corner makes each square belong to one cell and makes the entry depend only on cells above and to the left, the usual grid filling order. A 0 cell gets $dp[i][j] = 0$, and a 1 in the first row or column gets 1, since no larger square fits. Otherwise the entry comes from the three neighbours. The answer is the largest entry squared: the largest square can end anywhere, not only at the last cell.

Why the minimum? A $k \times k$ square with corner $(i, j)$ contains three $(k-1) \times (k-1)$ squares, ending at $(i-1, j)$, $(i, j-1)$, and $(i-1, j-1)$. So each neighbour's value must be at least $k - 1$, which gives $dp[i][j] \le 1 + \min$ of the three. The reverse also holds: if all three are at least $s$, their squares together with cell $(i, j)$ cover a full $(s+1) \times (s+1)$ square. The bound is therefore exact. Using max or a sum instead would claim squares that extend over 0 cells, because one large neighbour says nothing about the rows or columns the other two must cover.