FAANG Coding Interview Mastery: Dynamic Programming Patterns
Dynamic Programming (DP) is one of the most frequently tested topics in FAANG interviews. This guide systematically covers the DP patterns you must know to succeed.
1. The DP Framework
How to Recognize DP Problems
Dynamic programming problems have two core properties.
**Optimal Substructure**
- The optimal solution to the whole problem can be built from optimal solutions to subproblems
- Example: The shortest path A→C equals the shortest A→B plus shortest B→C
**Overlapping Subproblems**
- The same subproblems are solved multiple times
- Fibonacci: fib(5) = fib(4) + fib(3), fib(4) = fib(3) + fib(2) → fib(3) is computed twice
DP Recognition Signals
- Problems asking for "maximum", "minimum", "longest", or "shortest"
- Counting problems: "how many ways can you...?"
- Feasibility problems: "is it possible to...?"
- Problems exploring substructures of arrays or strings
Top-down vs Bottom-up Comparison
Top-down (Memoization) - Recursion + Cache
def fib_topdown(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_topdown(n-1, memo) + fib_topdown(n-2, memo)
return memo[n]
Bottom-up (Tabulation) - Iteration + Table
def fib_bottomup(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
| Property | Top-down | Bottom-up |
| ------------ | ----------------------------- | ---------------------------- |
| Approach | Recursion + Memoization | Iteration + Table |
| Intuition | Natural problem decomposition | Must determine order upfront |
| Space | Call stack overhead | Table space only |
| Speed | Computes only needed states | Computes all states |
| Optimization | Harder | Space optimization possible |
4-Step DP Design
1. **State Definition**: Clearly define what dp[i] represents
2. **Recurrence**: Express dp[i] in terms of previous states
3. **Base Cases**: Set up initial values
4. **Computation Order**: Determine order based on dependencies
2. 1D DP Patterns
Climbing Stairs (LeetCode 70)
def climbStairs(n: int) -> int:
if n <= 2:
return n
dp[i] = number of ways to reach step i
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
Space optimized: O(n) -> O(1)
def climbStairs_optimized(n: int) -> int:
if n <= 2:
return n
prev, curr = 1, 2
for _ in range(3, n + 1):
prev, curr = curr, prev + curr
return curr
- Time: O(n)
- Space: O(1) (optimized version)
House Robber (LeetCode 198)
def rob(nums: list) -> int:
if not nums:
return 0
if len(nums) == 1:
return nums[0]
dp[i] = max money robbed from houses 0..i
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]
Space optimized
def rob_optimized(nums: list) -> int:
prev2, prev1 = 0, 0
for num in nums:
prev2, prev1 = prev1, max(prev1, prev2 + num)
return prev1
House Robber II (LeetCode 213)
Circular array: cannot select both the first and last house simultaneously.
def rob2(nums: list) -> int:
def rob_linear(houses):
prev2, prev1 = 0, 0
for h in houses:
prev2, prev1 = prev1, max(prev1, prev2 + h)
return prev1
if len(nums) == 1:
return nums[0]
Include first house (exclude last) vs include last house (exclude first)
return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))
Maximum Product Subarray (LeetCode 152)
Because of negatives, we must track both minimum and maximum.
def maxProduct(nums: list) -> int:
max_prod = min_prod = result = nums[0]
for num in nums[1:]:
Negative * negative minimum = positive maximum
candidates = (num, max_prod * num, min_prod * num)
max_prod = max(candidates)
min_prod = min(candidates)
result = max(result, max_prod)
return result
- Time: O(n)
- Space: O(1)
Jump Game I and II (LeetCode 55, 45)
Jump Game I: Can you reach the last index?
def canJump(nums: list) -> bool:
max_reach = 0
for i, jump in enumerate(nums):
if i > max_reach:
return False
max_reach = max(max_reach, i + jump)
return True
Jump Game II: Minimum jumps to reach end
def jump(nums: list) -> int:
jumps = current_end = farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == current_end:
jumps += 1
current_end = farthest
return jumps
Longest Increasing Subsequence (LeetCode 300)
O(n^2) DP approach
def lengthOfLIS(nums: list) -> int:
n = len(nums)
dp[i] = length of LIS ending at index i
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
O(n log n) binary search approach
def lengthOfLIS_nlogn(nums: list) -> int:
tails = []
for num in nums:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)
3. 2D DP Patterns
Unique Paths (LeetCode 62)
def uniquePaths(m: int, n: int) -> int:
dp[i][j] = number of paths from (0,0) to (i,j)
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
Space optimized: 1D array
def uniquePaths_optimized(m: int, n: int) -> int:
dp = [1] * n
for _ in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1]
return dp[-1]
Minimum Path Sum (LeetCode 64)
def minPathSum(grid: list) -> int:
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = grid[0][0]
Initialize first row
for j in range(1, n):
dp[0][j] = dp[0][j-1] + grid[0][j]
Initialize first column
for i in range(1, m):
dp[i][0] = dp[i-1][0] + grid[i][0]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[m-1][n-1]
Longest Common Subsequence (LeetCode 1143)
def longestCommonSubsequence(text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
dp[i][j] = LCS length of text1[:i] and text2[:j]
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
- Time: O(m \* n)
- Space: O(m \* n), optimizable to O(min(m, n))
Edit Distance (LeetCode 72)
def minDistance(word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp[i][j] = min operations to convert word1[:i] to word2[:j]
dp = [[0] * (n + 1) for _ in range(m + 1)]
Base cases
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(
dp[i-1][j], # delete
dp[i][j-1], # insert
dp[i-1][j-1] # replace
)
return dp[m][n]
Coin Change (LeetCode 322)
def coinChange(coins: list, amount: int) -> int:
dp[i] = minimum coins needed to make amount i
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
Coin Change 2 (LeetCode 518)
def change(amount: int, coins: list) -> int:
dp[i] = number of ways to make amount i (unbounded knapsack)
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]
return dp[amount]
0/1 Knapsack
def knapsack(weights: list, values: list, capacity: int) -> int:
n = len(weights)
dp[i][w] = max value using first i items with capacity w
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
dp[i][w] = dp[i-1][w] # do not take item i
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1])
return dp[n][capacity]
Space optimized: traverse in reverse
def knapsack_optimized(weights: list, values: list, capacity: int) -> int:
dp = [0] * (capacity + 1)
for i in range(len(weights)):
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
4. Interval DP
Interval DP finds the optimal solution for a contiguous subarray or substring [i, j].
Key insight: **dp[i][j] = optimal value for the range i to j**
Burst Balloons (LeetCode 312)
def maxCoins(nums: list) -> int:
Add virtual 1s at both ends
nums = [1] + nums + [1]
n = len(nums)
dp[i][j] = max coins from bursting all balloons in nums[i+1..j-1]
dp = [[0] * n for _ in range(n)]
Start from length 2 (no balloons between adjacent boundaries)
for length in range(2, n):
for left in range(n - length):
right = left + length
for k in range(left + 1, right):
k is the LAST balloon burst in interval [left, right]
coins = nums[left] * nums[k] * nums[right]
dp[left][right] = max(
dp[left][right],
dp[left][k] + coins + dp[k][right]
)
return dp[0][n-1]
- Time: O(n^3)
- Space: O(n^2)
Palindromic Substrings (LeetCode 647)
def countSubstrings(s: str) -> int:
n = len(s)
dp[i][j] = True if s[i..j] is a palindrome
dp = [[False] * n for _ in range(n)]
count = 0
Length 1: always palindrome
for i in range(n):
dp[i][i] = True
count += 1
Length 2
for i in range(n - 1):
if s[i] == s[i+1]:
dp[i][i+1] = True
count += 1
Length 3+
for length in range(3, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = True
count += 1
return count
Longest Palindromic Subsequence (LeetCode 516)
def longestPalindromeSubseq(s: str) -> int:
n = len(s)
dp[i][j] = length of longest palindromic subsequence in s[i..j]
dp = [[0] * n for _ in range(n)]
Length 1: always 1
for i in range(n):
dp[i][i] = 1
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]
Matrix Chain Multiplication Concept
Find the order of multiplying matrices A1 _ A2 _ ... \* An that minimizes total operations.
- dp[i][j] = minimum operations to multiply matrices i through j
- Recurrence: `dp[i][j] = min(dp[i][k] + dp[k+1][j] + dims[i-1] * dims[k] * dims[j])` with `i <= k < j`
5. DP on Trees and Graphs
House Robber III (LeetCode 337)
Find the maximum sum on a tree where no two adjacent nodes can be selected.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rob3(root: TreeNode) -> int:
def dfs(node):
if not node:
return (0, 0) # (not robbed, robbed)
left_no, left_yes = dfs(node.left)
right_no, right_yes = dfs(node.right)
Skip this node: children can be either robbed or not
not_rob = max(left_no, left_yes) + max(right_no, right_yes)
Rob this node: children cannot be robbed
rob = node.val + left_no + right_no
return (not_rob, rob)
return max(dfs(root))
Unique Binary Search Trees (LeetCode 96)
def numTrees(n: int) -> int:
dp[i] = number of structurally unique BSTs with i nodes (Catalan number)
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for nodes in range(2, n + 1):
for root in range(1, nodes + 1):
left_count = dp[root - 1]
right_count = dp[nodes - root]
dp[nodes] += left_count * right_count
return dp[n]
6. FAANG DP Interview Trends
Google favors Hard DP problems.
- Burst Balloons, Regular Expression Matching, Wildcard Matching
- Problems with complex state spaces (3D DP)
- Interval DP or bitmask DP
**Prep tip**: Practice starting with recursion, adding memoization, then converting to tabulation.
Meta (Facebook)
Practical Medium DP problems are common.
- Coin Change, Longest Common Subsequence
- Decode Ways, Word Break
- Product-adjacent DP problems
**Prep tip**: Code clarity and communication matter most. Explain the recurrence before writing code.
Amazon
Practical Medium DP problems dominate.
- House Robber series, Jump Game
- Longest Increasing Subsequence, Maximum Subarray
- Optimization problems linked to system design
**Prep tip**: Connect algorithm explanations to Leadership Principles when possible.
State Space Optimization
Many 2D DP problems can be reduced to 1D.
LCS: 2D to 1D optimization
def lcs_optimized(text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
if m < n:
text1, text2 = text2, text1
m, n = n, m
Keep only previous row
prev = [0] * (n + 1)
for i in range(1, m + 1):
curr = [0] * (n + 1)
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
curr[j] = prev[j-1] + 1
else:
curr[j] = max(prev[j], curr[j-1])
prev = curr
return prev[n]
**Optimization Principles**:
- Current row depends only on previous row → Rolling array (2D → 1D)
- Current value depends only on immediately previous → Two variables (1D → O(1))
- Reverse traversal saves space in 0/1 Knapsack
7. Practice Quiz
**Answer**: House Robber
**Explanation**: dp[i] represents the maximum money that can be robbed from houses 0 to i. If we rob house i, we cannot rob house i-1, so we take dp[i-2] + nums[i]. If we skip house i, we take dp[i-1]. We maximize over both choices.
**Answer**: Because zero coins are needed to make amount 0.
**Explanation**: dp[0] = 0 is the base case. Zero amount requires no coins at all. All other states dp[1], dp[2], etc. are built on this foundation. If dp[0] were not 0, every computed value would be incorrect.
**Answer**: When text1[i-1] == text2[j-1], i.e., the current characters being compared are equal.
**Explanation**: When two characters match, we can extend the LCS found so far by one character, giving dp[i-1][j-1] + 1. When they do not match, we take max(dp[i-1][j], dp[i][j-1]), meaning we skip one character from either string.
**Answer**: To ensure subproblems are independent of each other.
**Explanation**: If k were defined as the first balloon burst, then after bursting it, the neighbors change, making the two resulting subproblems interdependent. By defining k as the last balloon, intervals [left, k] and [k, right] are completely independent, and the score when k is burst last is always nums[left] _ nums[k] _ nums[right].
**Answer**: tails[i] is the smallest tail element of all increasing subsequences of length i+1.
**Explanation**: The tails array does not store an actual LIS. Instead, it stores the minimum possible tail value for each subsequence length. This allows binary search to find in O(log n) where a new number fits. The final length of tails equals the length of the LIS.
Summary
Dynamic programming becomes systematic once you internalize the patterns.
**Recommended Learning Order**:
1. Climbing Stairs, Fibonacci (DP fundamentals)
2. House Robber series (1D DP)
3. Unique Paths, Minimum Path Sum (2D DP)
4. LCS, Edit Distance (String DP)
5. Coin Change (Knapsack)
6. Burst Balloons (Interval DP)
7. House Robber III (Tree DP)
**Interview Tips**:
- Always start by defining the state
- Verbalize the recurrence before writing code
- Progress from Brute Force to Memoization to Tabulation
- Always analyze time and space complexity
현재 단락 (1/345)
Dynamic Programming (DP) is one of the most frequently tested topics in FAANG interviews. This guide...