Dynamic Programming — Visual Guide

1-D DP · leetcode 509 · easy

The Fibonacci sequence is defined such that each number is the sum of the two preceding ones, starting from 0 and 1. Given n, return F(n).
This is the canonical DP warm-up: the recurrence is handed to you directly, so the only skill being tested is whether you can trade the exponential recursion tree for a linear table.

examples n = 6 → F(0)=0, F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5, F(6)=8
n = 10 → 55

Subproblem

dp[i] = the i-th Fibonacci number

Recurrence

dp[i] = dp[i-1] + dp[i-2]
dp[0] = 0, dp[1] = 1

n =

Press Next step to begin filling the table.

step 0

filled

source cells

current

answer

time: O(n) space: O(n) → O(1) optimized pattern: linear 1D DP

Notes

Key Insight

Every value depends only on the two before it. The table is just the recurrence written out flat.

Complexity

Time: O(n) | Space: O(n) → O(1) with two variables

Pattern

Linear 1-D DP

Edge Cases

n=0 → 0; n=1 → 1; large n may overflow 32-bit int

1-D DP · leetcode 70 · easy

You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. In how many distinct ways can you reach the top?
The recurrence ends up identical to Fibonacci, but the reasoning is different — you arrive at step i either from step i-1 (1-step) or step i-2 (2-step), so the number of ways is the sum of those two subproblems.

examples n = 3 → [1+1+1, 1+2, 2+1] = 3 ways
n = 5 → 8 ways

Subproblem

dp[i] = number of ways to reach stair i

Recurrence

dp[i] = dp[i-1] + dp[i-2]
dp[1] = 1, dp[2] = 2

n stairs =

Press Next step to begin filling the table.

step 0

filled

source cells

current

answer

time: O(n) space: O(n) → O(1) optimized pattern: linear 1D DP

Notes

Key Insight

Identical recurrence to Fibonacci, but the reasoning differs — you arrive at step i from i-1 or i-2.

Complexity

Time: O(n) | Space: O(n) → O(1)

Pattern

Linear 1-D DP

Edge Cases

n=1 → 1 way; n=2 → 2 ways

1-D DP · leetcode 198 · medium

You are a robber planning to rob houses along a street. Each house has a certain amount of money. Adjacent houses have security alarms connected — if you rob two adjacent houses, the alarm triggers. Given an integer array nums representing the money in each house, return the maximum amount you can rob tonight without triggering any alarm.
At each house you make a binary decision: rob it (skip the previous) or skip it (carry forward the best so far).

examples nums = [2, 7, 9, 3, 1] → rob houses 0, 2, 4: 2+9+1 = 12
nums = [1, 2, 3, 1] → rob houses 0, 2: 1+3 = 4

Subproblem

dp[i] = max money robbing houses 0..i

Recurrence

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

houses =

Press Next step to begin. Adjacent houses have alarms — you can't rob two in a row.

step 0

filled

source cells

current

answer

time: O(n) space: O(n) → O(1) optimized pattern: decision at each step

Notes

Key Insight

At each house, the choice is binary: rob it (skip previous) or skip it (carry best so far). No lookahead needed.

Complexity

Time: O(n) | Space: O(n) → O(1)

Pattern

Decision at each step (1-D DP)

Edge Cases

Empty array → 0; single house → that value; two houses → max of both

2-D DP · leetcode 322 · medium

Given an integer array coins of different denominations and an integer amount, return the fewest number of coins needed to make up that amount. If it's impossible, return -1. You may assume you have an infinite supply of each coin.
The table's rows are coin types (first i coins available), columns are amounts (0 .. amount). At every cell you make one decision: skip this coin, or use it (and, since coins are unbounded, stay on the same row). This is the classic unbounded-knapsack shape.

examples coins = [1, 2, 5], amount = 11 → 5 + 5 + 1 → 3
coins = [2], amount = 3 → impossible → -1

Subproblem

dp[i][j] = min coins to make amount j using first i coin types

Recurrence

dp[i][j] = min(dp[i-1][j], dp[i][j - coins[i-1]] + 1)
dp[0][0] = 0, dp[0][j>0] = ∞, dp[i][0] = 0

coins = amount =

Press Next step to begin. Each cell asks: using only the first i coins, what's the min number of coins that sum to j?

step 0

skip coin (i-1)

use coin (j - c)

current

answer

time: O(n · amount) space: O(n · amount) → O(amount) optimized pattern: unbounded knapsack

Notes

Key Insight

Two choices per cell: skip this coin (inherit dp[i-1][j]) or use it (add 1 to dp[i][j-coin], same row because coins are unbounded).

Complexity

Time: O(n · amount) | Space: O(n · amount), collapses to O(amount)

Pattern

Unbounded knapsack — each row reads only from itself and the previous row, so it flattens to 1-D.

Edge Cases

amount=0 → 0; row 0 (no coins) = ∞ for j>0; unreachable final cell → -1

2-D DP · leetcode 1143 · medium

Given two strings s1 and s2, return the length of their longest common subsequence (LCS). A subsequence is derived from a string by deleting some characters (possibly none) without changing the relative order of the remaining characters.
The 2D table encodes the answer to every pair of prefixes. When characters match, we extend the diagonal; when they don't, we take the best from the row above or the column to the left.

examples s1 = "ABCBDAB", s2 = "BDCAB" → LCS = "BCAB" → length 4
s1 = "ace", s2 = "abcde" → LCS = "ace" → length 3

Subproblem

dp[i][j] = LCS length of s1[0..i-1] and s2[0..j-1]

Recurrence

if s1[i-1]==s2[j-1]: dp[i-1][j-1]+1
else: max(dp[i-1][j], dp[i][j-1])

s1 = s2 =

Press Next step to begin. Each cell asks: what's the longest common subsequence up to these two prefixes?

step 0

same row (i-1)

same col (j-1)

current

answer

time: O(m·n) space: O(m·n) pattern: 2D match/skip

Notes

Key Insight

When characters match, extend the diagonal. When they don't, take the better of skipping one character from either string.

Complexity

Time: O(m·n) | Space: O(m·n) → O(min(m,n)) with rolling row

Pattern

2-D match/skip DP

Edge Cases

Either string empty → 0; identical strings → full length; no common chars → 0

2-D DP · leetcode 72 · hard

Given two words word1 and word2, return the minimum number of operations to convert word1 into word2. You have three operations, each costing 1: insert a character, delete a character, or replace a character.
Each cell dp[i][j] asks: "what's the cheapest way to align the first i characters of word1 with the first j characters of word2?" If the current characters match, it's free (take the diagonal); otherwise, pay 1 and pick the cheapest of the three operations.

examples word1 = "horse", word2 = "ros" → horse→rorse→rose→ros = 3 ops
word1 = "intention", word2 = "execution" → 5 ops

Subproblem

dp[i][j] = min edits to convert word1[0..i-1] → word2[0..j-1]

Recurrence

if w1[i-1]==w2[j-1]: dp[i-1][j-1]
else: 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

word1 = word2 =

Press Next step to begin. Three operations allowed: insert, delete, replace (each costs 1).

step 0

delete (row above)

insert (col left)

current

answer

time: O(m·n) space: O(m·n) pattern: 2D min-cost transformation

Notes

Key Insight

If characters match it's free (take diagonal). Otherwise pay 1 and pick the cheapest of insert, delete, or replace.

Complexity

Time: O(m·n) | Space: O(m·n) → O(min(m,n))

Pattern

2-D min-cost transformation DP

Edge Cases

One string empty → length of other; identical strings → 0