Dynamic Programming (DP)

Algorithmic paradigm for solving optimization problems with overlapping subproblems

Hard Algorithm Optimal substructure Overlapping subproblems Memoization

Dynamic Programming (DP)

Overview

Dynamic Programming is an algorithmic paradigm that solves complex problems by breaking them down into simpler subproblems and storing their solutions to avoid redundant computations.

Key Properties

  • Time Complexity: Problem-specific, typically O(n²) or O(n³)
  • Space Complexity: O(n) to O(n²) for memoization table
  • Core Idea: Trade space for time by memoizing overlapping subproblems
  • When to Use: Problems with optimal substructure and overlapping subproblems
  • Key Techniques: Memoization (top-down) and Tabulation (bottom-up)

Core Characteristics

  • Optimal Substructure: Optimal solution contains optimal solutions to subproblems
  • Overlapping Subproblems: Same subproblems solved multiple times
  • Memoization: Store results to avoid recomputation
  • State Transition: Define relationship between states

References

Problem Categories

Category 1: Linear DP

  • Description: Single sequence problems with linear dependencies
  • Examples: LC 70 (Climbing Stairs), LC 198 (House Robber), LC 300 (LIS)
  • Pattern: dp[i] depends on dp[i-1], dp[i-2], etc.

Category 2: Grid/2D DP

  • Description: Problems on 2D grids or matrices
  • Examples: LC 62 (Unique Paths), LC 64 (Minimum Path Sum), LC 221 (Maximal Square)
  • Pattern: dp[i][j] depends on neighbors

Category 3: Interval DP

  • Description: Problems on intervals or subarrays
  • Examples: LC 312 (Burst Balloons), LC 1000 (Minimum Cost to Merge Stones)
  • Pattern: dp[i][j] for interval [i, j]

Category 4: Tree DP

  • Description: DP on tree structures
  • Examples: LC 337 (House Robber III), LC 968 (Binary Tree Cameras)
  • Pattern: State at each node depends on children

Category 5: State Machine DP

  • Description: Problems with multiple states and transitions
  • Examples: LC 714 (Stock with Fee), LC 309 (Stock with Cooldown)
  • Pattern: Multiple DP arrays for different states

Category 6: Knapsack DP

  • Description: Selection problems with constraints
  • Examples: LC 416 (Partition Equal Subset), LC 494 (Target Sum)
  • Pattern: dp[i][j] for items and capacity/target

Templates & Algorithms

Template Comparison Table

| Template Type | Use Case | State Definition | When to Use | |—————|———-|——————|————-| | 1D Linear | Single sequence | dp[i] = state at position i | Fibonacci-like problems | | 2D Grid | Matrix paths | dp[i][j] = state at (i,j) | Path counting, min/max | | Interval | Subarray/substring | dp[i][j] = [i,j] interval | Palindrome, partition | | Knapsack | Selection with limit | dp[i][w] = items & weight | 0/1, unbounded selection | | State Machine | Multiple states | dp[i][state] = at i in state | Buy/sell stocks |

Universal DP Template

def dp_solution(input_data):
    # Step 1: Define state
    # dp[i] represents...
    
    # Step 2: Initialize base cases
    dp = initialize_dp_array()
    dp[0] = base_value
    
    # Step 3: State transition
    for i in range(1, n):
        # Apply recurrence relation
        dp[i] = f(dp[i-1], dp[i-2], ...)
    
    # Step 4: Return answer
    return dp[n-1]

Template 1: 1D Linear DP

def linear_dp(nums):
    """Classic 1D DP for sequence problems"""
    n = len(nums)
    if n == 0:
        return 0
    
    # State: dp[i] = optimal value at position i
    dp = [0] * n
    dp[0] = nums[0]
    
    for i in range(1, n):
        # Transition: current vs previous
        dp[i] = max(dp[i-1], nums[i])
        # Or with skip: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    
    return dp[n-1]

Template 2: 2D Grid DP

def grid_dp(grid):
    """2D DP for grid/matrix problems"""
    if not grid or not grid[0]:
        return 0
    
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    
    # Initialize first row and column
    dp[0][0] = grid[0][0]
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    
    # Fill DP table
    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]

Template 3: Interval DP

def interval_dp(arr):
    """DP for interval/subarray problems"""
    n = len(arr)
    # dp[i][j] = optimal value for interval [i, j]
    dp = [[0] * n for _ in range(n)]
    
    # Base case: single elements
    for i in range(n):
        dp[i][i] = arr[i]
    
    # Iterate by interval length
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # Try all split points
            for k in range(i, j):
                dp[i][j] = max(dp[i][j], 
                              dp[i][k] + dp[k+1][j] + cost(i, j))
    
    return dp[0][n-1]

Template 4: 0/1 Knapsack

def knapsack_01(weights, values, capacity):
    """0/1 Knapsack problem"""
    n = len(weights)
    # dp[i][w] = max value with first i items, capacity w
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # Don't take item i-1
            dp[i][w] = dp[i-1][w]
            # Take item i-1 if possible
            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]

Template 5: State Machine DP

def state_machine_dp(prices, fee=0):
    """DP with multiple states (stock problems)"""
    if not prices:
        return 0
    
    n = len(prices)
    # States: hold stock, not hold stock
    hold = -prices[0]
    cash = 0
    
    for i in range(1, n):
        # Transition between states
        prev_hold = hold
        hold = max(hold, cash - prices[i])  # Buy
        cash = max(cash, prev_hold + prices[i] - fee)  # Sell
    
    return cash

Template 6: Top-Down Memoization

def top_down_dp(nums):
    """Top-down DP with memoization"""
    memo = {}
    
    def dp(i):
        # Base case
        if i < 0:
            return 0
        if i == 0:
            return nums[0]
        
        # Check memo
        if i in memo:
            return memo[i]
        
        # Recurrence relation
        result = max(dp(i-1), dp(i-2) + nums[i])
        memo[i] = result
        return result
    
    return dp(len(nums) - 1)

Problems by Pattern

Linear DP Problems

| Problem | LC # | Key Technique | Difficulty | |———|——|—————|————| | Climbing Stairs | 70 | dp[i] = dp[i-1] + dp[i-2] | Easy | | House Robber | 198 | Max with skip | Medium | | Longest Increasing Subsequence | 300 | O(n²) or O(nlogn) | Medium | | Maximum Subarray | 53 | Kadane’s algorithm | Easy | | Decode Ways | 91 | String DP | Medium | | Word Break | 139 | Dictionary DP | Medium | | Coin Change | 322 | Min coins | Medium |

2D Grid Problems

| Problem | LC # | Key Technique | Difficulty | |———|——|—————|————| | Unique Paths | 62 | Path counting | Medium | | Minimum Path Sum | 64 | Min cost path | Medium | | Maximal Square | 221 | 2D expansion | Medium | | Dungeon Game | 174 | Backward DP | Hard | | Cherry Pickup | 741 | 3D DP | Hard | | Number of Paths with Max Score | 1301 | Multi-value DP | Hard |

Interval DP Problems

| Problem | LC # | Key Technique | Difficulty | |———|——|—————|————| | Longest Palindromic Substring | 5 | Expand or DP | Medium | | Palindrome Partitioning II | 132 | Min cuts | Hard | | Burst Balloons | 312 | Interval multiplication | Hard | | Minimum Cost to Merge Stones | 1000 | K-way merge | Hard | | Strange Printer | 664 | Interval printing | Hard |

Knapsack Problems

| Problem | LC # | Key Technique | Difficulty | |———|——|—————|————| | Partition Equal Subset Sum | 416 | 0/1 Knapsack | Medium | | Target Sum | 494 | Sum to target | Medium | | Last Stone Weight II | 1049 | Min difference | Medium | | Ones and Zeroes | 474 | 2D Knapsack | Medium | | Coin Change 2 | 518 | Unbounded knapsack | Medium |

State Machine Problems

| Problem | LC # | Key Technique | Difficulty | |———|——|—————|————| | Best Time to Buy and Sell Stock II | 122 | Multiple transactions | Easy | | Stock with Cooldown | 309 | State transitions | Medium | | Stock with Transaction Fee | 714 | Fee consideration | Medium | | Stock III | 123 | At most 2 transactions | Hard | | Stock IV | 188 | At most k transactions | Hard |

LC Examples

2-1) Unique Paths

// java

// LC 62
// V0
// IDEA: 2D DP (fixed by gpt)
public int uniquePaths(int m, int n) {
    if (m == 0 || n == 0)
        return 0;

    int[][] dp = new int[m][n];

    /**  NOTE !!! init val as below
     *
     *  -> First row and first column = 1 path
     *    (only one way to go right/down)
     */
    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (int j = 0; j < n; j++) {
        dp[0][j] = 1;
    }

    // Fill the rest of the DP table
    // NOTE !!! i, j both start from 1
    // `(0, y), (x, 0)` already been initialized
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            /**  DP equation
             *
             *   dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
             */
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    return dp[m - 1][n - 1];
}

# 62. Unique Paths
# V0
# IDEA : BFS + dp (memory)
class Solution:
    def uniquePaths(self, m, n):

        # NOTE !!! we init paths as below
        paths = [[1]*n for _ in range(m)]
        
        q = deque()
        q.append((0,0))
        
        while q:
            row, col = q.popleft()
            
            if row == m or col == n or paths[row][col] > 1:
                continue 
            
            if row-1 >= 0 and col-1 >= 0:
                paths[row][col] = paths[row-1][col] + paths[row][col-1]
            
            q.append((row+1, col))
            q.append((row, col+1))
        
        return paths[-1][-1]

# V0'
# IDEA : DP
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        d = [[1] * n for _ in range(m)]

        for col in range(1, m):
            for row in range(1, n):
                d[col][row] = d[col - 1][row] + d[col][row - 1]

        return d[m - 1][n - 1]

2-2) Maximum Product Subarray

# NOTE : there is also brute force approach
# V0
# IDEA : brute force + product
class Solution(object):
    def maxProduct(self, A):
        global_max, local_max, local_min = float("-inf"), 1, 1
        for x in A:
            local_max = max(1, local_max)
            if x > 0:
                local_max, local_min = local_max * x, local_min * x
            else:
                local_max, local_min = local_min * x, local_max * x
            global_max = max(global_max, local_max)
        return global_max

# V1
# IDEA : BRUTE FORCE (TLE)
# https://leetcode.com/problems/maximum-product-subarray/solution/
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0

        result = nums[0]

        for i in range(len(nums)):
            accu = 1
            for j in range(i, len(nums)):
                accu *= nums[j]
                result = max(result, accu)

        return result

# V1
# IDEA : DP
# https://leetcode.com/problems/maximum-product-subarray/solution/
# LC 152
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0

        max_so_far = nums[0]
        min_so_far = nums[0]
        result = max_so_far

        for i in range(1, len(nums)):
            curr = nums[i]
            temp_max = max(curr, max_so_far * curr, min_so_far * curr)
            min_so_far = min(curr, max_so_far * curr, min_so_far * curr)

            max_so_far = temp_max

            result = max(max_so_far, result)

        return result

// java
// LC 152

// V0
// IDEA : DP
// https://github.com/yennanliu/CS_basics/blob/master/leetcode_python/Dynamic_Programming/maximum-product-subarray.py#L69
// IDEA : cur max = max (cur, cur * dp[k-1])
//        But, also needs to consider "minus number"
//        -> e.g.  (-1) * (-3) = 3
//        -> so we NEED to track maxSoFar, and minSoFar
public int maxProduct(int[] nums) {

    // null check
    if (nums.length == 0){
        return 0;
    }
    // init
    int maxSoFar = nums[0];
    int minSoFar = nums[0];
    int res = maxSoFar;

    for (int i = 1; i < nums.length; i++){

        int cur = nums[i];
        /**
         *  or, can use below trick to get max in 3 numbers
         *
         *   max = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]);
         *   min = Math.min(Math.min(temp * nums[i], min * nums[i]), nums[i]);
         *
         */
        int tmpMax = findMax(cur, maxSoFar * cur, minSoFar * cur);
        minSoFar = findMin(cur, maxSoFar * cur, minSoFar * cur);
        maxSoFar = tmpMax;

        res = Math.max(maxSoFar, res);
    }

    return res;
}

private int findMax(int a, int b, int c){
    if (a >= b && a >= c){
        return a;
    }
    else if (b >= a && b >= c){
        return b;
    }else{
        return c;
    }
}

private int findMin(int a, int b, int c){
    if (a <= b && a <= c){
        return a;
    }
    else if (b <= a && b <= c){
        return b;
    }else{
        return c;
    }
}

2-3) Best Time to Buy and Sell Stock with Transaction Fee

// java
// LC 714

  // V0-1
  // IDEA: DP (gpt)
  /**
   * Solution Explanation:
   *
   *
   *  -  Use two variables to represent the state:
   *      1. hold: The maximum profit achievable
   *               while holding a stock at day i.
   *
   *      2. cash: The maximum profit achievable
   *               while not holding a stock at day i.
   *
   *  - Transition equations:
   *    - If holding a stock:
   *       hold = max(hold, cash - price[i])
   *
   *       NOTE: 2 cases we hold th stock: 1) already hold from previous day 2) buy a new stock today
   *       (`hold`: You already held the stock from a previous day -> If you decided not to make any changes today, then the profit remains the same as the previous hold.)
   *       (`cash - price[i]`: You buy the stock today -> To buy the stock today, you need to spend money, reducing your profit. The cost to buy the stock is prices[i]. However, the amount of money you can spend is the maximum profit you had when you were not holding a stock previously (cash).)
   *
   * (You either keep holding or buy a new stock.)
   *    - If not holding a stock:
   *       cash = max(cash, hold + price[i] - fee)
   *
   *
   * (You either keep not holding or sell the stock and pay the fee.)
   *    - Initialize:
   *       - hold = -prices[0] (If you buy the stock on the first day).
   *       -  cash = 0 (You haven’t made any transactions yet).
   *
   */
  /**
   *  Example Walkthrough:
   *
   * Input:
   *    •   Prices: [1, 3, 2, 8, 4, 9]
   *    •   Fee: 2
   *
   * Steps:
   *    1.  Day 0:
   *    •   hold = -1 (Buy the stock at price 1).
   *    •   cash = 0.
   *    2.  Day 1:
   *    •   cash = max(0, -1 + 3 - 2) = 0 (No selling since profit is 0).
   *    •   hold = max(-1, 0 - 3) = -1 (No buying since it’s already better to hold).
   *    3.  Day 2:
   *    •   cash = max(0, -1 + 2 - 2) = 0.
   *    •   hold = max(-1, 0 - 2) = -1.
   *    4.  Day 3:
   *    •   cash = max(0, -1 + 8 - 2) = 5 (Sell at price 8).
   *    •   hold = max(-1, 5 - 8) = -1.
   *    5.  Day 4:
   *    •   cash = max(5, -1 + 4 - 2) = 5.
   *    •   hold = max(-1, 5 - 4) = 1.
   *    6.  Day 5:
   *    •   cash = max(5, 1 + 9 - 2) = 8 (Sell at price 9).
   *    •   hold = max(1, 5 - 9) = 1.
   *
   * Output:
   *    •   cash = 8 (Max profit).
   *
   */
  public int maxProfit_0_1(int[] prices, int fee) {
        // Edge case
        if (prices == null || prices.length == 0) {
            return 0;
        }

        // Initialize states
        int hold = -prices[0]; // Maximum profit when holding a stock
        int cash = 0; // Maximum profit when not holding a stock

        // Iterate through prices
        for (int i = 1; i < prices.length; i++) {
            /**
             *  NOTE !!! there are 2 dp equations (e.g. cash, hold)
             */
            // Update cash and hold states
            cash = Math.max(cash, hold + prices[i] - fee); // Sell the stock
            hold = Math.max(hold, cash - prices[i]); // Buy the stock
        }

        // The maximum profit at the end is when not holding any stock
        return cash;
    }

2-3) N-th Tribonacci Number

// java
// LC 1137. N-th Tribonacci Number

// V0
// IDEA: DP (fixed by gpt)
public int tribonacci(int n) {
    if (n == 0)
        return 0;
    if (n == 1 || n == 2)
        return 1;

    // NOTE !!! below, array size is `n + 1`
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 1;

    // NOTE !!! below, we loop from i = 3 to `i <= n`
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }

    return dp[n];
}

Decision Framework

Pattern Selection Strategy

DP Problem Identification Flowchart:

1. Can the problem be broken into subproblems?
   ├── NO → Not a DP problem
   └── YES → Continue to 2

2. Do subproblems overlap?
   ├── NO → Use Divide & Conquer
   └── YES → Continue to 3

3. Does it have optimal substructure?
   ├── NO → Not a DP problem
   └── YES → Use DP, continue to 4

4. What type of DP pattern?
   ├── Single sequence → Linear DP (Template 1)
   ├── 2D grid/matrix → Grid DP (Template 2)
   ├── Interval/substring → Interval DP (Template 3)
   ├── Selection with limit → Knapsack (Template 4)
   └── Multiple states → State Machine (Template 5)

5. Implementation approach?
   ├── Recursive structure clear → Top-down memoization
   └── Iterative structure clear → Bottom-up tabulation

When to Use DP vs Other Approaches

Problem Type Use DP Use Alternative Alternative
Optimization (min/max) ✅ Sometimes Greedy if optimal
Count ways/paths ✅ - -
Decision (yes/no) ✅ Sometimes Greedy/DFS
All solutions needed ❌ ✅ Backtracking
No overlapping subproblems ❌ ✅ Divide & Conquer
Greedy choice property ❌ ✅ Greedy

Summary & Quick Reference

Complexity Quick Reference

| Pattern | Time Complexity | Space Complexity | Space Optimization | |———|—————–|——————|——————-| | 1D Linear | O(n) | O(n) | O(1) with variables | | 2D Grid | O(m×n) | O(m×n) | O(n) with rolling array | | Interval | O(n³) typical | O(n²) | Usually not possible | | 0/1 Knapsack | O(n×W) | O(n×W) | O(W) with 1D array | | State Machine | O(n×k) | O(k) | Already optimized |

State Definition Guidelines

# 1D: Position/index based
dp[i] = "optimal value considering first i elements"

# 2D: Two dimensions
dp[i][j] = "optimal value for subproblem (i, j)"

# Interval: Range based  
dp[i][j] = "optimal value for interval [i, j]"

# Boolean: Decision problems
dp[i] = "whether target i is achievable"

Common Recurrence Relations

Sum/Count Patterns

# Fibonacci-like
dp[i] = dp[i-1] + dp[i-2]

# Include/exclude current
dp[i] = dp[i-1] + (dp[i-2] + nums[i])

Min/Max Patterns

# Take or skip
dp[i] = max(dp[i-1], dp[i-2] + nums[i])

# Best from all previous
dp[i] = max(dp[j] + score(j, i) for j < i)

Grid Patterns

# Path counting
dp[i][j] = dp[i-1][j] + dp[i][j-1]

# Min path
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

Problem-Solving Steps

  1. Identify if DP applicable: Check for overlapping subproblems
  2. Define state: What does dp[i] represent?
  3. Find recurrence: How do states relate?
  4. Identify base cases: Initial values
  5. Determine iteration order: Bottom-up direction
  6. Optimize space: Can we use rolling array?

Common Mistakes & Tips

🚫 Common Mistakes:

  • Wrong state definition
  • Missing base cases
  • Incorrect iteration order
  • Not handling edge cases
  • Integer overflow in large problems

✅ Best Practices:

  • Start with recursive solution, then optimize
  • Draw small examples to find patterns
  • Check array bounds carefully
  • Consider space optimization after correctness
  • Use meaningful variable names for states

Space Optimization Techniques

Rolling Array

# From O(n²) to O(n)
# Instead of dp[i][j], use dp[2][j]
curr = [0] * n
prev = [0] * n
for i in range(m):
    curr, prev = prev, curr
    # Update curr based on prev

State Compression

# From O(n) to O(1) for Fibonacci-like
prev2, prev1 = 0, 1
for i in range(2, n):
    curr = prev1 + prev2
    prev2, prev1 = prev1, curr

Interview Tips

  1. Start simple: Write recursive solution first
  2. Identify subproblems: Draw recursion tree
  3. Add memoization: Convert to top-down DP
  4. Consider bottom-up: Often more efficient
  5. Optimize space: Impress with rolling array
  6. Test with examples: Trace through small inputs
  • Greedy: When local optimal leads to global
  • Backtracking: When need all solutions
  • Divide & Conquer: No overlapping subproblems
  • Graph Algorithms: DP on graphs (shortest path)
  • Binary Search: Optimization problems with monotonicity