Split View: FAANG 코딩 인터뷰 완전 정복: 동적 프로그래밍 패턴

FAANG 코딩 인터뷰 완전 정복: 동적 프로그래밍 패턴

동적 프로그래밍(DP)은 FAANG 인터뷰에서 가장 자주 출제되는 주제 중 하나입니다. 이 글에서는 인터뷰에서 반드시 알아야 할 DP 패턴을 체계적으로 정리합니다.

1. DP 접근법 체계

DP 문제 인식하는 법

동적 프로그래밍 문제는 두 가지 핵심 특성을 가집니다.

최적 부분 구조 (Optimal Substructure)

전체 문제의 최적해가 부분 문제의 최적해로 구성됩니다
예: 최단 경로 문제에서 A→C 최단 경로는 A→B + B→C 최단 경로의 합

중복 부분 문제 (Overlapping Subproblems)

같은 부분 문제가 여러 번 반복하여 등장합니다
피보나치 수열: fib(5) = fib(4) + fib(3), fib(4) = fib(3) + fib(2) → fib(3)이 중복

DP 문제 인식 신호

"최대", "최소", "최장", "최단"을 구하는 문제
"몇 가지 방법이 있는가?" 같은 카운팅 문제
"가능한가?" 같은 가능성 판별 문제
배열, 문자열에서 부분 구조를 탐색하는 문제

Top-down vs Bottom-up 비교

# Top-down (Memoization) - 재귀 + 캐시
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) - 반복문 + 테이블
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]

특성	Top-down	Bottom-up
구현 방식	재귀 + 메모이제이션	반복문 + 테이블
직관성	문제를 자연스럽게 분해	순서를 먼저 파악해야 함
공간	콜스택 오버헤드	테이블 공간만
속도	필요한 부분만 계산	모든 상태 계산
최적화	어려움	공간 최적화 가능

DP 설계 4단계

상태 정의: dp[i]가 무엇을 의미하는지 명확히 정의
점화식: dp[i]를 이전 상태로 표현
초기값: 기저 사례(base case) 설정
계산 순서: 의존 관계에 따라 계산 순서 결정

2. 1D DP 패턴

Climbing Stairs (LeetCode 70)

def climbStairs(n: int) -> int:
    if n <= 2:
        return n
    # dp[i] = 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]

# 공간 최적화: 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

시간 복잡도: O(n)
공간 복잡도: O(1) (최적화 버전)

House Robber (LeetCode 198)

def rob(nums: list) -> int:
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    # dp[i] = 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]

# 공간 최적화
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)

원형 배열 처리: 첫 번째 집과 마지막 집을 동시에 선택 불가

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]
    # 첫 번째 집 포함 (마지막 집 제외) vs 마지막 집 포함 (첫 번째 집 제외)
    return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))

Maximum Product Subarray (LeetCode 152)

음수가 있으므로 최솟값도 추적해야 합니다.

def maxProduct(nums: list) -> int:
    max_prod = min_prod = result = nums[0]
    for num in nums[1:]:
        # 음수 * 음수(최솟값) = 양수(최댓값)이 될 수 있음
        candidates = (num, max_prod * num, min_prod * num)
        max_prod = max(candidates)
        min_prod = min(candidates)
        result = max(result, max_prod)
    return result

시간 복잡도: O(n)
공간 복잡도: O(1)

Jump Game I & II (LeetCode 55, 45)

# Jump Game I: 도달 가능한지 판별
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: 최소 점프 횟수
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 방법
def lengthOfLIS(nums: list) -> int:
    n = len(nums)
    # dp[i] = nums[i]로 끝나는 LIS의 길이
    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) 이진 탐색 방법
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 패턴

Unique Paths (LeetCode 62)

def uniquePaths(m: int, n: int) -> int:
    # dp[i][j] = (0,0)에서 (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]

# 공간 최적화: 1D 배열
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]
    # 첫 행 초기화
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    # 첫 열 초기화
    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] = text1[:i]와 text2[:j]의 LCS 길이
    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]

시간 복잡도: O(m * n)
공간 복잡도: O(m * n), 최적화 시 O(min(m, n))

Edit Distance (LeetCode 72)

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    # dp[i][j] = word1[:i]를 word2[:j]로 변환하는 최소 연산 수
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    # 기저 사례
    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],    # 삭제
                    dp[i][j-1],    # 삽입
                    dp[i-1][j-1]   # 교체
                )
    return dp[m][n]

Coin Change (LeetCode 322)

def coinChange(coins: list, amount: int) -> int:
    # dp[i] = 금액 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] = 금액 i를 만드는 방법의 수 (완전 배낭 문제)
    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] = i번째 물건까지 고려할 때 무게 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]  # 선택 안 함
            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]

# 공간 최적화: 역방향 순회
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. 구간 DP (Interval DP)

구간 DP는 배열의 특정 구간 [i, j]에 대한 최적 해를 구하는 패턴입니다. 핵심: dp[i][j] = 구간 i부터 j까지의 최적값

Burst Balloons (LeetCode 312)

def maxCoins(nums: list) -> int:
    # 양 끝에 가상의 1 추가
    nums = [1] + nums + [1]
    n = len(nums)
    # dp[i][j] = nums[i+1..j-1] 구간의 풍선을 모두 터뜨려 얻는 최대 동전
    dp = [[0] * n for _ in range(n)]

    # 구간 길이 2부터 시작 (인접한 두 경계 사이에 풍선이 없음)
    for length in range(2, n):
        for left in range(n - length):
            right = left + length
            for k in range(left + 1, right):
                # k번 풍선을 구간 [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]

시간 복잡도: O(n^3)
공간 복잡도: O(n^2)

Palindromic Substrings (LeetCode 647)

def countSubstrings(s: str) -> int:
    n = len(s)
    # dp[i][j] = s[i..j]가 팰린드롬이면 True
    dp = [[False] * n for _ in range(n)]
    count = 0

    # 길이 1: 항상 팰린드롬
    for i in range(n):
        dp[i][i] = True
        count += 1

    # 길이 2
    for i in range(n - 1):
        if s[i] == s[i+1]:
            dp[i][i+1] = True
            count += 1

    # 길이 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] = s[i..j]에서 가장 긴 팰린드롬 부분 수열의 길이
    dp = [[0] * n for _ in range(n)]

    # 길이 1: 항상 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 개념

행렬 A1 _ A2 _ ... * An의 곱셈 횟수를 최소화하는 문제입니다.

dp[i][j] = 행렬 i부터 j까지 곱할 때의 최소 연산 수
점화식: 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)

트리에서 인접한 노드를 동시에 선택할 수 없을 때 최대 합을 구합니다.

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)  # (선택 안 함, 선택함)

        left_no, left_yes = dfs(node.left)
        right_no, right_yes = dfs(node.right)

        # 현재 노드를 선택하지 않으면: 자식들 각각의 최댓값 합
        not_rob = max(left_no, left_yes) + max(right_no, right_yes)
        # 현재 노드를 선택하면: 자식들은 선택 불가
        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] = i개의 노드로 만들 수 있는 BST의 수 (카탈란 수)
    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 출제 경향

Google

Google은 Hard 난이도의 DP 문제를 선호합니다.

Burst Balloons, Regular Expression Matching, Wildcard Matching
상태 공간이 복잡한 문제 (3D DP 등)
구간 DP나 비트마스크 DP

준비 팁: 재귀에서 시작해 메모이제이션을 추가하고, 마지막에 Bottom-up으로 변환하는 과정을 연습하세요.

Meta (Facebook)

Medium 난이도의 실용적인 DP 문제가 많습니다.

Coin Change, Longest Common Subsequence
Decode Ways, Word Break
실제 제품 설계와 연관된 DP 문제

준비 팁: 코드 간결성과 설명 능력이 중요합니다. 점화식을 먼저 설명하고 코드를 작성하세요.

Amazon

실용적인 Medium DP 문제가 주로 출제됩니다.

House Robber 시리즈, Jump Game
Longest Increasing Subsequence, Maximum Subarray
시스템 디자인과 연계된 최적화 문제

준비 팁: 리더십 원칙과 함께 알고리즘 설명을 연결하면 좋습니다.

상태 공간 최적화

많은 2D DP를 1D로 최적화할 수 있습니다.

# LCS 2D -> 1D 최적화
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
    # 이전 행만 유지
    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]

최적화 원칙:

현재 행이 이전 행에만 의존 → 롤링 배열 (2D → 1D)
현재 값이 바로 이전 값에만 의존 → 변수 2개 (1D → O(1))
역방향 순회로 공간 절약 (0/1 Knapsack)

7. 연습 문제 퀴즈

퀴즈 1: 다음 중 dp[i] = max(dp[i-1], dp[i-2] + nums[i])로 정의되는 문제는?

정답: House Robber

설명: dp[i]는 i번째 집까지 고려할 때 훔칠 수 있는 최대 금액입니다. i번째 집을 선택하면 i-1번째 집은 선택 불가하므로 dp[i-2] + nums[i], 선택하지 않으면 dp[i-1]이 됩니다.

퀴즈 2: Coin Change 문제에서 dp[0] = 0으로 초기화하는 이유는?

정답: 금액 0을 만드는 데 필요한 동전 수는 0이기 때문입니다.

설명: dp[0] = 0은 기저 사례로, 금액 0은 아무 동전도 사용하지 않아도 됩니다. dp[1], dp[2], ...는 dp[0]을 기반으로 계산됩니다. 만약 dp[0] = 0이 아니면 모든 값이 잘못 계산됩니다.

퀴즈 3: LCS에서 dp[i][j] = dp[i-1][j-1] + 1 조건은 언제 성립하나?

정답: text1[i-1] == text2[j-1]일 때, 즉 현재 비교하는 두 문자가 같을 때

설명: 두 문자가 같으면 이전까지의 LCS에 현재 문자를 추가할 수 있으므로 dp[i-1][j-1] + 1이 됩니다. 다를 경우에는 max(dp[i-1][j], dp[i][j-1])을 취합니다.

퀴즈 4: Burst Balloons에서 k를 "마지막으로 터뜨리는 풍선"으로 정의하는 이유는?

정답: 독립적인 부분 문제로 분리하기 위해서입니다.

설명: k를 "처음 터뜨리는 풍선"으로 정의하면 터뜨린 후 이웃이 변경되어 부분 문제가 독립적이지 않게 됩니다. 반면 k를 "마지막 풍선"으로 정의하면 [left, k]와 [k, right] 구간이 각자 독립적으로 계산 가능하며, k가 마지막에 터질 때의 점수는 항상 nums[left] _ nums[k] _ nums[right]로 고정됩니다.

퀴즈 5: O(n log n)의 LIS 알고리즘에서 tails 배열이 의미하는 것은?

정답: tails[i]는 길이 i+1인 증가 부분 수열에서 가능한 가장 작은 끝값입니다.

설명: tails 배열은 실제 LIS를 나타내지 않고, 각 길이의 LIS가 끝날 수 있는 가장 작은 값을 저장합니다. 이를 통해 이진 탐색으로 새로운 숫자가 어디에 삽입될지 O(log n)에 찾을 수 있습니다. tails 배열의 최종 길이가 LIS의 길이입니다.

마무리

동적 프로그래밍은 처음에는 어렵게 느껴지지만, 패턴을 익히면 체계적으로 접근할 수 있습니다.

학습 순서 추천:

Climbing Stairs, Fibonacci (DP 기초)
House Robber 시리즈 (1D DP)
Unique Paths, Minimum Path Sum (2D DP)
LCS, Edit Distance (문자열 DP)
Coin Change (배낭 문제)
Burst Balloons (구간 DP)
House Robber III (트리 DP)

인터뷰 팁:

항상 상태 정의부터 시작하세요
점화식을 말로 설명하고 코드를 작성하세요
Brute force → Memoization → Tabulation 순서로 최적화하세요
시간/공간 복잡도를 항상 분석하세요

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