Dynamic Programming: The Patterns Behind the Problems

Dynamic programming has a reputation for being hard to learn. I think it's actually one of the most learnable topics in DSA — once you realize that most DP problems belong to a small set of pattern families, and recognizing the family is 80% of the solution.

Here are the five families I reach for most often.

1. Linear DP (1D array, left-to-right transitions)

Canonical problem: Climbing Stairs, House Robber, Maximum Subarray

The shape: dp[i] depends on a fixed number of previous values.

dp[i] = f(dp[i-1], dp[i-2], ...)

Recognition signal: "At each step, you have a small number of choices based on your recent history."

House Robber is the clearest example:

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

You either skip the current house (take dp[i-1]) or rob it (take dp[i-2] + nums[i]).

2. Grid DP (2D array, top-left to bottom-right)

Canonical problem: Unique Paths, Minimum Path Sum, Dungeon Game

The shape: dp[i][j] depends on values from the cell above and/or to the left.

Recognition signal: "You're navigating a grid from one corner to another, accumulating some cost or count."

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

3. Interval DP (compute answers for subranges, build up to the full range)

Canonical problem: Burst Balloons, Matrix Chain Multiplication, Minimum Cost to Merge Stones

The shape: dp[i][j] = answer for the subarray from i to j, computed from smaller intervals.

for length in range(2, n+1):
    for i in range(n - length + 1):
        j = i + length - 1
        for k in range(i, j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost(i,j))

Recognition signal: "The problem involves merging or splitting an array/string optimally."

4. Knapsack DP (choose a subset under a capacity constraint)

Canonical problem: 0/1 Knapsack, Coin Change, Partition Equal Subset Sum

The shape: dp[i][w] = best value using the first i items with weight capacity w.

Recognition signal: "Choose items (or amounts) to maximize/minimize a value given a total constraint."

The key transition for 0/1 knapsack:

dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])

5. State machine DP (discrete states, transition costs)

Canonical problem: Best Time to Buy and Sell Stock with Cooldown, Jump Game variants

The shape: Multiple dp arrays, one per state (e.g., holding, sold, rest).

Recognition signal: "Your valid actions at each step depend on what state you're currently in."

Stock with cooldown:

holding[i] = max(holding[i-1], rest[i-1] - prices[i])
sold[i]    = holding[i-1] + prices[i]
rest[i]    = max(rest[i-1], sold[i-1])

The recognition meta-skill

When I see a new DP problem I ask:

1. Is there a 1D array with local transitions? → Linear DP
2. Is there a 2D grid with movement? → Grid DP
3. Am I optimizing over subarrays? → Interval DP
4. Am I selecting items under a constraint? → Knapsack DP
5. Do I have multiple modes of operation? → State machine DP

This doesn't cover every DP problem — there are tree DP, digit DP, and profile DP variants I haven't listed — but it covers the majority of what appears in interviews and competitive programming rounds up to Hard difficulty.

The best way to solidify these patterns is to solve three problems in each family back-to-back, explicitly noting which pattern you're using before you start coding. After 15 problems done this way, recognition becomes automatic.