Interview prep — dynamic programming

Visualize the subproblem

Step through five classic DP problems cell by cell. The key to DP is naming the subproblem before you write any code — the table fills itself once you have that.

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
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
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
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
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])
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
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])
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
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])
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