Dynamic Programming Pattern Guide for LeetCode

More DP

How To DP

1. Core DP Templates

Template 1: 1D Dynamic Programming

def one_dimensional_dp(n: int) -> int:
    # 1. Initialize DP array
    dp = [0] * (n + 1)

    # 2. Base cases
    dp[0] = base_case_0
    dp[1] = base_case_1

    # 3. State transition
    for i in range(2, n + 1):
        dp[i] = some_function(dp[i-1], dp[i-2])

    return dp[n]

Template 2: 2D Dynamic Programming

def two_dimensional_dp(m: int, n: int) -> int:
    # 1. Initialize 2D DP array
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 2. Base cases
    dp[0][0] = base_case

    # 3. State transition
    for i in range(m + 1):
        for j in range(n + 1):
            dp[i][j] = some_function(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

Template 3: State Compression (Space Optimization)

def space_optimized_dp(n: int) -> int:
    # Instead of full array, keep only needed states
    prev2, prev1 = base_case_0, base_case_1

    for i in range(2, n + 1):
        current = some_function(prev1, prev2)
        prev2, prev1 = prev1, current

    return prev1

2. LeetCode Problem Categories

Category 1: Linear Sequence DP

1. LeetCode 70: Climbing Stairs

def climbStairs(n: int) -> int:
    if n <= 2:
        return n

    prev2, prev1 = 1, 2
    for i in range(3, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current

    return prev1

1. LeetCode 198: House Robber

def rob(nums: List[int]) -> int:
    if not nums:
        return 0
    if len(nums) <= 2:
        return max(nums)

    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]

1. LeetCode 300: Longest Increasing Subsequence

Category 2: Matrix Path DP

1. LeetCode 64: Minimum Path Sum