Dynamic Programming Patterns: 1D, 2D, Memoization, and Tabulation

Dynamic programming solves problems by breaking them into overlapping subproblems and caching the results. If you find yourself writing a recursive solution where the same inputs are computed multiple times, DP is the answer. This guide covers the most common patterns with both memoization and tabulation approaches.

When to Use DP

A problem is a DP problem when it has:

1. Optimal substructure: The optimal solution can be built from optimal solutions to subproblems.
2. Overlapping subproblems: The same subproblems are solved multiple times.

Common signals: “minimum/maximum”, “count the number of ways”, “is it possible to”, “longest/shortest”.

Memoization vs Tabulation

Memoization (Top-Down):           Tabulation (Bottom-Up):
Start from the big problem        Start from base cases
Recurse into subproblems           Build up to the answer
Cache results in a dict/array      Fill a table iteratively
Only solves needed subproblems     Solves all subproblems
Risk of stack overflow             No recursion needed

Pattern 1: Linear DP (1D)

Climbing Stairs (LC 70)

You can climb 1 or 2 steps. How many distinct ways to reach the top?

# Memoization (top-down)
def climbStairs_memo(n: int) -> int:
    memo = {}
    
    def dp(i):
        if i <= 1:
            return 1
        if i in memo:
            return memo[i]
        memo[i] = dp(i - 1) + dp(i - 2)
        return memo[i]
    
    return dp(n)

# Tabulation (bottom-up)
def climbStairs(n: int) -> int:
    if n <= 1:
        return 1
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

# Space-optimized (only need last 2 values)
def climbStairs_opt(n: int) -> int:
    if n <= 1:
        return 1
    prev2, prev1 = 1, 1
    for _ in range(2, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    return prev1

print(climbStairs(5))  # 8

House Robber (LC 198)

You cannot rob two adjacent houses. Maximize the total money.

def rob(nums: list[int]) -> int:
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    # dp[i] = max money robbing houses 0..i
    # At each house: skip it (dp[i-1]) or rob it (dp[i-2] + nums[i])
    prev2, prev1 = 0, 0
    
    for num in nums:
        curr = max(prev1, prev2 + num)
        prev2, prev1 = prev1, curr
    
    return prev1

print(rob([2, 7, 9, 3, 1]))  # 12 (rob houses 0, 2, 4)

// Java version
public int rob(int[] nums) {
    int prev2 = 0, prev1 = 0;
    for (int num : nums) {
        int curr = Math.max(prev1, prev2 + num);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

Coin Change (LC 322)

Find the minimum number of coins to make a target amount.

def coinChange(coins: list[int], amount: int) -> int:
    # dp[i] = min coins needed for amount i
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
    
    return dp[amount] if dp[amount] != float('inf') else -1

print(coinChange([1, 5, 10, 25], 30))  # 2 (25 + 5)
print(coinChange([2], 3))              # -1

Longest Increasing Subsequence (LC 300)

def lengthOfLIS(nums: list[int]) -> 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) solution using binary search
import bisect

def lengthOfLIS_fast(nums: list[int]) -> 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)

print(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]))  # 4

Pattern 2: Decision DP

At each step, you make a choice and the state transitions depend on that choice.

Word Break (LC 139)

def wordBreak(s: str, wordDict: list[str]) -> bool:
    word_set = set(wordDict)
    n = len(s)
    # dp[i] = True if s[0:i] can be segmented
    dp = [False] * (n + 1)
    dp[0] = True
    
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    
    return dp[n]

print(wordBreak("leetcode", ["leet", "code"]))       # True
print(wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"]))  # False

Pattern 3: 2D DP (Grid Problems)

Unique Paths (LC 62)

Count the number of paths from top-left to bottom-right in an m x n grid.

def uniquePaths(m: int, n: int) -> int:
    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: only need previous row
def uniquePaths_opt(m: int, n: int) -> int:
    row = [1] * n
    for _ in range(1, m):
        for j in range(1, n):
            row[j] += row[j - 1]
    return row[n - 1]

print(uniquePaths(3, 7))  # 28

Minimum Path Sum (LC 64)

def minPathSum(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    
    # Fill first row
    for j in range(1, n):
        grid[0][j] += grid[0][j - 1]
    
    # Fill first column
    for i in range(1, m):
        grid[i][0] += grid[i - 1][0]
    
    # Fill rest
    for i in range(1, m):
        for j in range(1, n):
            grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])
    
    return grid[m - 1][n - 1]

print(minPathSum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]))  # 7

Pattern 4: String DP

Longest Common Subsequence (LC 1143)

def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    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]

print(longestCommonSubsequence("abcde", "ace"))  # 3 ("ace")

// Java version
public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1))
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
}

Edit Distance (LC 72)

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    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],       # delete
                    dp[i][j - 1],       # insert
                    dp[i - 1][j - 1]    # replace
                )
    
    return dp[m][n]

print(minDistance("horse", "ros"))       # 3
print(minDistance("intention", "execution"))  # 5

Pattern 5: Knapsack

0/1 Knapsack

def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    n = len(weights)
    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]  # skip item
            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 (1D)
def knapsack_opt(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for w in range(capacity, weights[i] - 1, -1):  # reverse!
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]

print(knapsack([2, 3, 4, 5], [3, 4, 5, 6], 8))  # 10

Partition Equal Subset Sum (LC 416)

def canPartition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0:
        return False
    
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    
    for num in nums:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
    
    return dp[target]

print(canPartition([1, 5, 11, 5]))  # True (1+5+5=11)
print(canPartition([1, 2, 3, 5]))   # False

Space Optimization Techniques

Most 2D DP can be reduced to 1D when each row only depends on the previous row.

# 2D: O(m*n) space
dp = [[0] * (n + 1) for _ in range(m + 1)]

# 1D: O(n) space -- current row overwrites previous
dp = [0] * (n + 1)

# Key: iterate in reverse when each item can only be used once (0/1 knapsack)
# Iterate forward when items can be reused (unbounded knapsack)

DP Problem-Solving Framework

1. Define the state: What does dp[i] (or dp[i][j]) represent?
2. Find the recurrence: How does dp[i] relate to smaller subproblems?
3. Identify base cases: What are the smallest subproblems you can solve directly?
4. Determine iteration order: Which subproblems must be solved first?
5. Optimize space if needed: Can you reduce 2D to 1D?

Key Takeaways

Dynamic programming is about caching overlapping subproblems. Start with recursion, add memoization, then convert to tabulation for better performance. Linear DP problems use a 1D array and depend on a constant number of previous states. Grid and string DP use 2D arrays. Knapsack is a special case of decision DP where you include or exclude each item. Most 2D DP can be optimized to 1D space. The hardest part is defining the state and recurrence correctly — once you have those, the code follows mechanically.