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

State Definition: Clearly define what dp[i] represents
Recurrence: Express dp[i] in terms of previous states
Base Cases: Set up initial values
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
import bisect

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

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

Quiz 1: Which problem uses the recurrence dp[i] = max(dp[i-1], dp[i-2] + nums[i])?

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.

Quiz 2: Why do we initialize dp[0] = 0 in the Coin Change problem?

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.

Quiz 3: When does dp[i][j] = dp[i-1][j-1] + 1 hold in LCS?

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.

Quiz 4: Why do we define k as the LAST balloon burst in the Burst Balloons problem?

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

Quiz 5: What does the tails array represent in the O(n log n) LIS algorithm?

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:

Climbing Stairs, Fibonacci (DP fundamentals)
House Robber series (1D DP)
Unique Paths, Minimum Path Sum (2D DP)
LCS, Edit Distance (String DP)
Coin Change (Knapsack)
Burst Balloons (Interval DP)
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