Dynamic Programming: Solve Problems Optimally

DP Fundamentals & Theory

Dynamic Programming is an algorithmic technique to solve complex problems by breaking them into overlapping subproblems and storing solutions to avoid recomputation. It applies when two key properties hold.

Two Pillars of Dynamic Programming

DP requires two essential properties:

When to Use DP

Apply DP when: recursive structure with overlapping subproblems, need for optimal value (max/min/count), naive recursion is exponential, problem decomposes into independent subproblems.

Top-Down vs Bottom-Up

Top-Down Approach: Memoization

Write a recursive function, then cache results in a Dictionary to avoid recomputing subproblems. This mirrors natural problem thinking.

Memoization Template

private Dictionary<int, int> memo = new Dictionary<int, int>();

private int SolveHelper(int n) {
    // Check cache first
    if (memo.ContainsKey(n))
        return memo[n];

    // Base cases
    if (n == 0) return 0;
    if (n == 1) return 1;

    // Recurrence: solve subproblems recursively
    int result = SolveHelper(n - 1) + SolveHelper(n - 2);

    // Memoize before returning
    memo[n] = result;
    return result;
}

public int Solve(int n) {
    memo.Clear();
    return SolveHelper(n);
}

Fibonacci Example: Compute fib(n) using memoization. Without caching, fib(5) recomputes fib(3) twice. With caching, each subproblem solves once.

Memoization with 2D State

For problems with multiple dimensions (e.g., grid, sequence), use nested Dictionary or 2D array:

private Dictionary<string, int> memo = new Dictionary<string, int>();

private int SolveHelper(int i, int j) {
    // Create composite key for 2D state
    string key = $"{i},{j}";
    if (memo.ContainsKey(key))
        return memo[key];

    // Base cases and recurrence...
    int result = /* computation */ 0;
    memo[key] = result;
    return result;
}

Bottom-Up Approach: Tabulation

Build solutions iteratively from base cases upward. Fill a table/array with values, computing each state from previously solved states. No recursion, no stack overhead.

Tabulation Template (1D)

public int Solve(int n) {
    // Create DP table
    int[] dp = new int[n + 1];

    // Base cases
    dp[0] = 0;
    if (n > 0) dp[1] = 1;

    // Fill table bottom-up
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

Fibonacci via Tabulation: Build dp table from bottom. dp[0]=0, dp[1]=1, then dp[i]=dp[i-1]+dp[i-2]. Naturally avoids recomputation.

Tabulation Template (2D)

public int Solve(int m, int n) {
    // Create 2D DP table
    int[][] dp = new int[m][];
    for (int i = 0; i < m; i++)
        dp[i] = new int[n];

    // Initialize base cases
    for (int i = 0; i < m; i++)
        dp[i][0] = 1;
    for (int j = 0; j < n; j++)
        dp[0][j] = 1;

    // Fill table bottom-up
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }

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

Space Optimization Techniques

Many DP problems depend only on previous row/column. Replace O(m*n) space with O(n) using rolling arrays or variable optimization.

Rolling Array (1D Optimization)

If current state depends only on the previous state, maintain just two arrays: previous and current.

public int Solve(int m, int n) {
    // Only keep current and previous rows
    int[] prev = new int[n];
    int[] curr = new int[n];

    // Initialize base case for row 0
    for (int j = 0; j < n; j++)
        prev[j] = 1;

    // Fill rows from 1 to m-1
    for (int i = 1; i < m; i++) {
        curr[0] = 1;
        for (int j = 1; j < n; j++) {
            curr[j] = prev[j] + curr[j-1];
        }
        // Swap arrays
        int[] temp = prev;
        prev = curr;
        curr = temp;
    }

    return prev[n - 1];
}

Two-Variable Optimization

For problems where only two previous values matter (not a full row/column), reduce to O(1) space with two variables.

public int FibOptimized(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    int prev2 = 0, prev1 = 1, curr = 0;

    for (int i = 2; i <= n; i++) {
        curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }

    return curr;
}

1D DP: Climbing Stairs (LeetCode 70)

Problem: Climb n steps. At each step, climb 1 or 2 steps. How many distinct ways?

Problem Analysis

State Definition: dp[i] = number of ways to reach step i.

Recurrence Relation: dp[i] = dp[i-1] + dp[i-2] (reach step i from step i-1 or i-2).

Base Cases: dp[0] = 1 (one way to stay at step 0), dp[1] = 1 (one way to reach step 1).

Bottom-Up C# Solution

public int ClimbStairs(int n) {
    if (n <= 1) return 1;

    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;

    // Each step can be reached from step i-1 or i-2
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    return dp[n];
}

// Space-optimized version: O(1) space, O(n) time
public int ClimbStairsOptimized(int n) {
    if (n <= 1) return 1;

    int prev2 = 1, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

1D DP: House Robber I & II (LC 198, 213)

Problem I: Rob houses in a line. Can't rob adjacent houses. Maximize loot. Problem II: Houses arranged in a circle—first and last are adjacent.

House Robber I: Recurrence

State: dp[i] = max money robbing houses 0..i.

Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) (skip or rob house i).

House Robber I: Full Solution

public int Rob(int[] nums) {
    if (nums == null || nums.Length == 0) return 0;
    if (nums.Length == 1) return nums[0];

    int[] dp = new int[nums.Length];
    dp[0] = nums[0];
    dp[1] = Math.Max(nums[0], nums[1]);

    for (int i = 2; i < nums.Length; i++) {
        // Rob current house + max from i-2, or skip to take max from i-1
        dp[i] = Math.Max(dp[i-1], dp[i-2] + nums[i]);
    }

    return dp[nums.Length - 1];
}

// Space-optimized: only need prev2 and prev1
public int RobOptimized(int[] nums) {
    if (nums == null || nums.Length == 0) return 0;
    if (nums.Length == 1) return nums[0];

    int prev2 = nums[0];
    int prev1 = Math.Max(nums[0], nums[1]);

    for (int i = 2; i < nums.Length; i++) {
        int curr = Math.Max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }

    return prev1;
}

// House Robber II: houses in circle. Can't rob first and last together.
public int RobII(int[] nums) {
    if (nums == null || nums.Length == 0) return 0;
    if (nums.Length == 1) return nums[0];

    // Case 1: Rob houses 0 to n-2 (exclude last)
    int case1 = RobRange(nums, 0, nums.Length - 2);

    // Case 2: Rob houses 1 to n-1 (exclude first)
    int case2 = RobRange(nums, 1, nums.Length - 1);

    return Math.Max(case1, case2);
}

private int RobRange(int[] nums, int start, int end) {
    if (start > end) return 0;
    if (start == end) return nums[start];

    int prev2 = 0, prev1 = nums[start];

    for (int i = start + 1; i <= end; i++) {
        int curr = Math.Max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }

    return prev1;
}

1D DP: Coin Change (LC 322)

Problem: Given coins and amount. Find minimum number of coins to make amount. Return -1 if impossible.

State & Recurrence

State: dp[i] = minimum coins to make amount i.

Recurrence: dp[i] = 1 + min(dp[i-coin]) for each coin ≤ i.

Base Case: dp[0] = 0 (zero coins for zero amount).

Full Solution

public int CoinChange(int[] coins, int amount) {
    // dp[i] = min coins to make amount i
    int[] dp = new int[amount + 1];

    // Initialize: mark impossible amounts
    for (int i = 1; i <= amount; i++)
        dp[i] = amount + 1; // Use amount+1 as "infinity"

    dp[0] = 0;

    // Fill table: for each amount
    for (int i = 1; i <= amount; i++) {
        // Try each coin
        foreach (int coin in coins) {
            if (coin <= i) {
                // Can use this coin
                dp[i] = Math.Min(dp[i], 1 + dp[i - coin]);
            }
        }
    }

    return dp[amount] > amount ? -1 : dp[amount];
}

1D DP: Longest Increasing Subsequence (LC 300)

Problem: Find longest strictly increasing subsequence. Return length.

Approach 1: O(n²) DP Solution

State: dp[i] = length of LIS ending at index i.

Recurrence: dp[i] = 1 + max(dp[j]) for all j < i where nums[j] < nums[i].

public int LengthOfLIS(int[] nums) {
    if (nums == null || nums.Length == 0) return 0;

    int[] dp = new int[nums.Length];
    int maxLen = 0;

    for (int i = 0; i < nums.Length; i++) {
        dp[i] = 1; // At minimum, LIS ending at i has length 1

        // Check all previous elements
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.Max(dp[i], 1 + dp[j]);
            }
        }

        maxLen = Math.Max(maxLen, dp[i]);
    }

    return maxLen;
}

// Approach 2: O(n log n) using binary search
public int LengthOfLISOptimal(int[] nums) {
    if (nums == null || nums.Length == 0) return 0;

    List<int> tails = new List<int>();

    // tails[i] = smallest tail element for LIS of length i+1
    foreach (int num in nums) {
        int pos = tails.BinarySearch(num);
        if (pos < 0) {
            pos = ~pos; // Convert to insertion position
        }
        if (pos == tails.Count) {
            tails.Add(num);
        } else {
            tails[pos] = num;
        }
    }

    return tails.Count;
}

1D DP: Word Break & Decode Ways (LC 139, 91)

Word Break: Can segment string using dictionary words? Decode Ways: Count number of ways to decode digit string (1=A, 2=B, ..., 26=Z).

Word Break Solution (LC 139)

State: dp[i] = true if s[0..i-1] can be segmented.

Recurrence: dp[i] = true if ∃j where dp[j]=true and s[j..i-1] is in dictionary.

public bool WordBreak(string s, IList<string> wordDict) {
    HashSet<string> dict = new HashSet<string>(wordDict);
    bool[] dp = new bool[s.Length + 1];
    dp[0] = true;

    for (int i = 1; i <= s.Length; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dict.Contains(s.Substring(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[s.Length];
}

// Decode Ways (LC 91)
// State: dp[i] = number of ways to decode s[0..i-1]
// Recurrence: dp[i] = dp[i-1] (if s[i-1] is 1-9) + dp[i-2] (if s[i-2..i-1] is 10-26)
public int NumDecodings(string s) {
    if (s == null || s.Length == 0 || s[0] == '0') return 0;

    int n = s.Length;
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        // Check single digit (1-9)
        if (s[i - 1] != '0') {
            dp[i] += dp[i - 1];
        }

        // Check two digits (10-26)
        int twoDigit = int.Parse(s.Substring(i - 2, 2));
        if (twoDigit >= 10 && twoDigit <= 26) {
            dp[i] += dp[i - 2];
        }
    }

    return dp[n];
}

Perfect Squares (LC 279)

State: dp[i] = minimum perfect squares to sum to i.

public int NumSquares(int n) {
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++)
        dp[i] = i; // At worst: i = 1+1+...+1

    for (int i = 1; i <= n; i++) {
        // Try all perfect squares less than i
        for (int j = 1; j * j <= i; j++) {
            dp[i] = Math.Min(dp[i], 1 + dp[i - j * j]);
        }
    }

    return dp[n];
}

Partition Equal Subset Sum (LC 416)

Can array be partitioned into two subsets with equal sum? Classic knapsack disguised as subset problem.

public bool CanPartition(int[] nums) {
    int sum = 0;
    foreach (int num in nums) sum += num;

    // Odd sum: impossible to split equally
    if (sum % 2 != 0) return false;

    int target = sum / 2;
    bool[] dp = new bool[target + 1];
    dp[0] = true;

    foreach (int num in nums) {
        // Iterate backwards to avoid using same element twice
        for (int i = target; i >= num; i--) {
            dp[i] = dp[i] || dp[i - num];
        }
    }

    return dp[target];
}

2D DP: Grid & Path Problems

Unique Paths (LC 62) and Minimum Path Sum (LC 64)—fundamental 2D DP patterns for grids.

Unique Paths (LC 62)

State: dp[i][j] = number of paths from (0,0) to (i,j).

Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1] (from top or left).

public int UniquePaths(int m, int n) {
    int[][] dp = new int[m][];
    for (int i = 0; i < m; i++)
        dp[i] = new int[n];

    // Base case: first row and column have only 1 path
    for (int i = 0; i < m; i++) dp[i][0] = 1;
    for (int j = 0; j < n; j++) dp[0][j] = 1;

    // Fill table
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }

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

// Minimum Path Sum (LC 64)
// State: dp[i][j] = min sum path from (0,0) to (i,j)
// Recurrence: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
public int MinPathSum(int[][] grid) {
    int m = grid.Length;
    int n = grid[0].Length;

    int[][] dp = new int[m][];
    for (int i = 0; i < m; i++)
        dp[i] = new int[n];

    // Base cases
    dp[0][0] = grid[0][0];
    for (int i = 1; i < m; i++)
        dp[i][0] = dp[i-1][0] + grid[i][0];
    for (int j = 1; j < n; j++)
        dp[0][j] = dp[0][j-1] + grid[0][j];

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = grid[i][j] + Math.Min(dp[i-1][j], dp[i][j-1]);
        }
    }

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

2D DP: String Algorithms

Edit Distance (LC 72) and Longest Common Subsequence—fundamental string DP problems.

Edit Distance (LC 72)

State: dp[i][j] = min operations to convert s1[0..i-1] to s2[0..j-1].

public int MinDistance(string word1, string word2) {
    int m = word1.Length;
    int n = word2.Length;

    int[][] dp = new int[m + 1][];
    for (int i = 0; i <= m; i++)
        dp[i] = new int[n + 1];

    // Base cases
    for (int i = 0; i <= m; i++)
        dp[i][0] = i;
    for (int j = 0; j <= n; j++)
        dp[0][j] = j;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.Min(dp[i-1][j],
                            Math.Min(dp[i][j-1], dp[i-1][j-1]));
            }
        }
    }

    return dp[m][n];
}

Longest Common Subsequence (LC 1143)

State: dp[i][j] = length of LCS of text1[0..i-1] and text2[0..j-1].

public int LongestCommonSubsequence(string text1, string text2) {
    int m = text1.Length;
    int n = text2.Length;

    int[][] dp = new int[m + 1][];
    for (int i = 0; i <= m; i++)
        dp[i] = new int[n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = 1 + dp[i-1][j-1];
            } else {
                dp[i][j] = Math.Max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    return dp[m][n];
}

0/1 Knapsack & Variants

Classic 0/1 Knapsack with space optimization, and Longest Palindromic Substring (LC 5).

0/1 Knapsack with Space Optimization

public int Knapsack(int[] weights, int[] values, int capacity) {
    int[] dp = new int[capacity + 1];

    // For each item
    for (int i = 0; i < weights.Length; i++) {
        // Iterate backwards to avoid using item twice
        for (int w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.Max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }

    return dp[capacity];
}

// Longest Palindromic Substring (LC 5)
// State: dp[i][j] = true if s[i..j] is palindrome
public string LongestPalindrome(string s) {
    if (s == null || s.Length < 1) return "";

    int n = s.Length;
    bool[][] dp = new bool[n][];
    for (int i = 0; i < n; i++)
        dp[i] = new bool[n];

    int start = 0, maxLen = 1;

    // Single characters are palindromes
    for (int i = 0; i < n; i++)
        dp[i][i] = true;

    // Check palindromes of length 2 and more
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s[i] == s[j]) {
                dp[i][j] = (len == 2) || dp[i + 1][j - 1];
                if (dp[i][j] && len > maxLen) {
                    start = i;
                    maxLen = len;
                }
            }
        }
    }

    return s.Substring(start, maxLen);
}

Interval DP & State Machine DP

Burst Balloons (LC 312) and Buy Sell Stock with Cooldown (LC 309)—advanced DP patterns for interviews.

Burst Balloons (LC 312) Concept

State: dp[left][right] = max coins bursting balloons between left and right.

Key Insight: Think backwards—last balloon to burst determines the recurrence. When balloon k is last, left and right aren't adjacent until k bursts.

public int MaxCoins(int[] nums) {
    if (nums == null || nums.Length == 0) return 0;

    // Pad with 1s to handle boundary cases
    int[] balloons = new int[nums.Length + 2];
    balloons[0] = 1;
    balloons[balloons.Length - 1] = 1;
    for (int i = 0; i < nums.Length; i++)
        balloons[i + 1] = nums[i];

    int n = balloons.Length;
    int[][] dp = new int[n][];
    for (int i = 0; i < n; i++)
        dp[i] = new int[n];

    // len = distance between left and right
    for (int len = 2; len < n; len++) {
        for (int left = 0; left + len < n; left++) {
            int right = left + len;
            for (int k = left + 1; k < right; k++) {
                dp[left][right] = Math.Max(
                    dp[left][right],
                    dp[left][k] + balloons[left] * balloons[k] * balloons[right] + dp[k][right]
                );
            }
        }
    }

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

// Buy Sell Stock with Cooldown (LC 309)
// State machine: hold[i] = max profit on day i while holding stock
// sold[i] = max profit on day i after selling
// rest[i] = max profit on day i while not holding (cooling down)
public int MaxProfitCooldown(int[] prices) {
    if (prices == null || prices.Length <= 1) return 0;

    int hold = -prices[0]; // Buy on day 0
    int sold = 0;       // No stock sold yet
    int rest = 0;       // No action yet

    for (int i = 1; i < prices.Length; i++) {
        int prevHold = hold;
        int prevSold = sold;
        int prevRest = rest;

        // Today: hold stock (prev hold, or buy from rest)
        hold = Math.Max(prevHold, prevRest - prices[i]);

        // Today: sold stock (sell from hold)
        sold = prevHold + prices[i];

        // Today: rest (cooldown from sold, or continue rest)
        rest = Math.Max(prevSold, prevRest);
    }

    // Final state: either sold (best) or resting (no stock)
    return Math.Max(sold, rest);
}

Bitmask DP & Advanced Patterns

Use bitmask to represent visited subsets. Example: Traveling Salesman Problem variant.

Bitmask DP Template

Concept: dp[mask][i] = optimal value when visited cities in 'mask' and currently at city i.

// Template: Subset DP with bitmask
public int BitmaskDP(int n) {
    // dp[mask] = answer for subset represented by mask
    int[] dp = new int[1 << n];

    // Iterate through all subsets
    for (int mask = 0; mask < (1 << n); mask++) {
        // Check if bit i is set in mask
        for (int i = 0; i < n; i++) {
            if (((mask >> i) & 1) == 1) {
                // Bit i is set
                int prevMask = mask ^ (1 << i); // Remove bit i
                dp[mask] = Math.Max(dp[mask], dp[prevMask] + /* value */ 0);
            }
        }
    }

    return dp[(1 << n) - 1]; // All bits set
}

Pattern Recognition & Interview Tips

Common DP Problem Patterns

Interview Problem Recognition Checklist

• Overlapping subproblems: Will recursive solution recompute states?
• Optimal substructure: Does optimal solution contain optimal subsolutions?
• Recurrence relation: Can you express current state using previous states?
• Base cases: What are the smallest solvable instances?
• State definition: What minimal information defines a subproblem?
• Space optimization: Do you need full DP table or just previous values?

Interview Strategy

Common Mistakes

Detailed Problem Solutions Summary

This chapter covers comprehensive DP solutions:

• Section 12.1: DP Fundamentals—overlapping subproblems and optimal substructure theory
• Section 12.2: Top-Down Memoization—Dictionary caching, recursion-based approach
• Section 12.3: Bottom-Up Tabulation—iterative table-filling approach without recursion overhead
• Section 12.4: Space Optimization—rolling arrays and 2-variable reduction techniques
• Section 12.5: Climbing Stairs (LC 70)—basic 1D DP with closed-form recurrence
• Section 12.6: House Robber I & II (LC 198, 213)—linear and circular variants
• Section 12.7: Coin Change (LC 322)—unbounded knapsack min-coin problem
• Section 12.8: Longest Increasing Subsequence (LC 300)—O(n²) DP and O(n log n) binary search optimization
• Section 12.9: Word Break (LC 139) & Decode Ways (LC 91)—string segmentation and digit counting
• Section 12.10: Advanced 1D DP—Maximum Product Subarray, Perfect Squares, Partition Equal Subset Sum
• Section 12.11: 2D DP Grid Paths—Unique Paths (LC 62) and Minimum Path Sum (LC 64)
• Section 12.12: 2D DP Strings—Edit Distance (LC 72) and Longest Common Subsequence (LC 1143)
• Section 12.13: Knapsack Variants—0/1 Knapsack space optimization and Longest Palindromic Substring (LC 5)
• Section 12.14: Interval DP & State Machines—Burst Balloons (LC 312) and Buy Sell Stock with Cooldown (LC 309)
• Section 12.15: Bitmask DP—subset enumeration and iteration patterns
• Section 12.16: Pattern Recognition & Interview Tips—problem classification, recognition checklist, common mistakes

Key Formulas & State Definitions

Climbing Stairs: dp[i] = dp[i-1] + dp[i-2]

House Robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i])

Coin Change: dp[i] = 1 + min(dp[i-coin]) for all coins ≤ i

LIS: dp[i] = 1 + max(dp[j]) for all j < i where nums[j] < nums[i]

Edit Distance: dp[i][j] = dp[i-1][j-1] if s1[i-1]==s2[j-1], else 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

Knapsack: dp[w] = max(dp[w], dp[w-weight] + value)

Unique Paths: dp[i][j] = dp[i-1][j] + dp[i][j-1]

Interview Talking Points

Code Structure Best Practices

Private helper function with clear parameter meaning: Use private int DP(int index, bool holding) rather than private int DP(int x, int y). Clarity matters in interviews.

Boundary condition checks first: Always validate null/empty input before accessing arrays.

Comment recurrence logic: Interviewers appreciate seeing you understand the transition, not just the code.

Test with examples: Walk through a small example (n=2 or n=3) while coding. This catches off-by-one errors.

Advanced DP Techniques Not Covered

Topics beyond this chapter's scope (but good for advanced interview prep):

• Convex Hull Trick: Optimize linear DP transitions from O(n²) to O(n log n)
• Divide & Conquer Optimization: Monotone queue DP (LC 1099)
• Profile Dynamic Programming: Tiling problems (LC 1240)
• Digit DP: Count integers with specific properties (LC 233)
• Tree DP: Rerooting and subtree DP on trees
• Polynomial Hashing + DP: String matching with DP

Space Optimization Deep Dive

When original dp is O(n²): If dp[i][j] depends only on dp[i-1][...], use rolling array (swap two 1D arrays each iteration).

When original dp is O(n): If dp[i] depends only on dp[i-1] and dp[i-2], use two variables.

Trade-off consideration: Optimization makes code harder to read. In interview, implement correct O(n²) solution first; offer space optimization as enhancement if time permits.

Common DP Problem Variants

Count ways: dp[i] += (number of ways to reach i). Sum transitions.

Maximum value: dp[i] = max(dp[i], candidate). Compare transitions.

Minimum value: dp[i] = min(dp[i], candidate). Choose smallest transition.

Existence (true/false): dp[i] = OR of (all valid transitions). Boolean OR logic.

Related Algorithms & When to Use

Greedy vs DP: Greedy optimal locally (never revisit choice). DP explores all paths. Use DP when greedy fails.

Divide & Conquer vs DP: D&C solves non-overlapping subproblems (mergesort). DP memoizes overlapping subproblems. Check for overlap.

BFS/DFS vs DP: Graph shortest path? Use BFS/Dijkstra. Counting paths with constraints? DP is cleaner.

Debugging DP Solutions

Print table during execution: Add logging to see how dp table fills. Helps verify recurrence is correct.

Test edge cases: n=0, n=1, empty array, single element, all same value.

Verify base cases: Manually compute dp[0], dp[1], dp[2] by hand. Match your code output.

Check off-by-one: Are you using 0-indexed or 1-indexed? Verify loop bounds: i < n vs i <= n.

Memory limits: For n=10^5, O(n²) space = 10^10 bytes = ~9 GB (too much). Use space optimization.

DP vs Memoization Performance Real Example

Fibonacci naive recursion: fib(40) takes ~10 seconds (exponential branches).

Fibonacci with memoization: fib(40) takes microseconds (compute each once).

Fibonacci iterative DP: fib(40) takes microseconds, no recursion stack risk.

This demonstrates why DP is essential for interview performance—naive recursion will timeout.

How to Present DP Solution in Interview

1. Clarify problem: "So I need to find the minimum coins to make amount X. Empty array returns 0, impossible returns -1."
2. Identify DP properties: "This has overlapping subproblems—amount 5 might be computed multiple times. And optimal substructure—optimal answer for amount 10 builds on optimal for amount 5."
3. Define state: "I'll use dp[i] = minimum coins to make amount i."
4. Write recurrence: "dp[i] = 1 + minimum of dp[i-coin] for each coin ≤ i."
5. Identify base case: "dp[0] = 0 because zero coins make zero amount."
6. Code solution: Write clean, commented code.
7. Trace example: "Let me trace coins=[1,2,5], amount=5: dp[0]=0, dp[1]=1, dp[2]=1, dp[3]=2, dp[4]=2, dp[5]=1. Result: 1."
8. Complexity analysis: "Time: O(amount × coins), Space: O(amount)."
9. Optimization suggestion: "We could optimize space to O(1) if we only need final answer, but current solution is clear."

30-Second DP Recognition Test

Can you recognize these as DP problems?

• ✓ "Count number of ways to..." → Count-based DP
• ✓ "Find maximum/minimum..." → Optimization DP
• ✓ "Can we achieve...?" → Boolean DP (reachability)
• ✓ "Word appears in dictionary" → String matching DP
• ✓ "Paths in grid avoiding obstacles" → Coordinate DP
• ✓ "Optimal arrangement/selection" → Knapsack or assignment DP
• ✗ "Find single shortest path in graph" → BFS/Dijkstra (not DP)
• ✗ "Sorted input, check if element exists" → Binary search (not DP)

Post-Interview Checklist

Before submitting:

• ✓ Tested on examples (n=0, n=1, small n)
• ✓ Checked array bounds (no IndexOutOfRangeException)
• ✓ Verified base cases match manual calculation
• ✓ Confirmed time/space complexity acceptable
• ✓ Code is readable with meaningful variable names
• ✓ No unnecessary recursion depth issues
• ✓ Handles all edge cases (empty input, impossible cases)

Time Complexity Cheatsheet

When to Choose Approach

Memoization (Top-Down): Natural recursion, smaller state space needed, interview clarity preferred.

Tabulation (Bottom-Up): Avoiding recursion depth limit, full state space needed, production code optimization.

Space Optimization: When you only need previous row/column or constant space. Always measure benefit vs. code clarity.

Beyond LeetCode: Real-World DP Applications

Bioinformatics: Sequence alignment (DNA/protein matching) uses edit distance DP extensively.

Natural Language Processing: Language models use DP for part-of-speech tagging (Viterbi algorithm).

Computer Vision: Image segmentation and object tracking rely on dynamic programming principles.

Operations Research: Supply chain optimization, resource allocation use integer programming (DP-based).

Compiler Design: Grammar parsing uses DP (CYK algorithm for context-free languages).

Final Wisdom: DP as Problem-Solving Framework

Dynamic Programming is not just a coding technique—it's a problem-solving philosophy:

• Break it down: Decompose large problems into subproblems.
• Reuse solutions: Don't recompute what you've already solved (memoization).
• Build upward: Solve smaller problems first, combine for larger ones.
• Avoid redundancy: Recognize when the same subproblem appears multiple times.

Mastering DP elevates your algorithmic thinking. You stop trying random approaches and systematically identify problem structure, define state, write recurrence. This discipline transfers across all coding interviews.

Practice Progression for Mastery

Week 1 - Foundations: Master Fibonacci, Climbing Stairs, simple 1D DP.

Week 2 - Classic Problems: House Robber, Coin Change, LIS. Understand both memoization and tabulation.

Week 3 - 2D DP: Grid paths, edit distance, LCS. Get comfortable with 2D table reasoning.

Week 4 - Optimization: Space optimization, binary search DP, more complex transitions.

Week 5 - Advanced: State machines (stock trading), interval DP (burst balloons), bitmask DP.

Week 6 - Mock Interviews: Solve new problems under time pressure. Practice explaining your solution.

Resources for Continued Learning

• LeetCode Tag: "Dynamic Programming" (100+ problems, sorted by difficulty)
• Codeforces: Educational Codeforces Rounds often feature DP problems
• Competitive Programming Books: "Competitive Programming" by Halim & Halim covers advanced DP
• Algorithm Design Manual (Skiena): Chapter on dynamic programming with real examples
• Open problem archive: AtCoder ABC/ARC for structured DP practice

Summary: The Complete DP Toolkit

You now have:

• ✓ Theoretical understanding of DP (overlapping subproblems, optimal substructure)
• ✓ Practical implementation skills (memoization, tabulation, space optimization)
• ✓ Solutions to 22+ classic interview problems
• ✓ Recognition patterns for 7 major DP paradigms
• ✓ Time/space complexity analysis
• ✓ Interview communication and debugging strategies
• ✓ Real-world application context

With this foundation, you're equipped to tackle DP problems confidently in technical interviews. Remember: when you see "find maximum/minimum/count," think DP.

Comprehensive Problem Index with Difficulty

State Definition Examples by Problem Type

Maximization: dp[i] = maximum value achievable up to i. Example: max profit from robbing houses.

Minimization: dp[i] = minimum cost/operations to reach i. Example: minimum coins for amount.

Counting: dp[i] = number of ways to achieve state i. Example: number of paths in grid.

Boolean: dp[i] = whether state i is reachable. Example: can word be segmented?

2D State: dp[i][j] = answer for subproblem with indices i and j. Example: dp[i][j] = LCS of first i and j characters.

3D State: dp[i][j][k] = answer with three independent dimensions. Example: stock buying with k transactions allowed.

Recurrence Relation Patterns

Linear (single transition): dp[i] = f(dp[i-1]). Simple chain.

Tree (multiple transitions): dp[i] = max/min(dp[i-1], dp[i-2], ...). Choose best among options.

Aggregate (sum): dp[i] = sum(dp[all valid j]). Count all possibilities.

Conditional: dp[i] = dp[i-1] if condition, else dp[i-2] + cost. Decision based on matching.

2D recurrence: dp[i][j] depends on dp[i-1][j], dp[i][j-1], dp[i-1][j-1]. Multi-directional.

Common Base Case Patterns

Zero-amount (knapsack): dp[0] = 0 (zero cost for zero amount).

Zero-length (string): dp[0] = 1 (one way to match empty string).

Single element (sequence): dp[1] = nums[0] or 1 (base step choice).

Impossible states: dp[i] = -1 or Integer.MAX_VALUE for unreachable states.

Grid boundaries: dp[0][0] = grid[0][0], dp[i][0] = sum of column 0, dp[0][j] = sum of row 0.

Transition Direction & Iteration Order

Forward iteration (i from 0 to n): Current state uses previous states. Example: dp[i] = f(dp[0..i-1]).

Backward iteration (i from n to 0): Used in 0/1 knapsack to avoid item reuse. Iterate weights backward.

Diagonal iteration: For interval DP, iterate by length (len = 2, 3, ..., n). Example: Burst Balloons.

Layered iteration: Outer loop by dimension 1, inner by dimension 2. Example: 2D grid problems.

Memoization vs Tabulation: Decision Tree

Do you need entire DP table for other operations? Yes → Tabulation. No → Memoization.

Is recursion depth a concern (n > 10,000)? Yes → Tabulation (avoid stack overflow). No → Either works.

Is state space sparse (not all states needed)? Yes → Memoization (compute only needed). No → Tabulation.

Do you want to optimize memory late? Yes → Tabulation (easier to optimize after). No → Memoization for clarity.

Edge Cases Checklist

• Empty input (null, empty array, empty string)
• Single element (array of length 1)
• All same values
• Negative numbers (if problem allows)
• Zero in array (if problem allows)
• Very large n (test if O(n²) will TLE)
• Impossible states (cannot reach target amount, cannot segment string)

Why DP Fails (and How to Fix)

Failure: TLE (Time Limit Exceeded): State space too large or transition too slow. Optimize recurrence or use advanced techniques (Convex Hull Trick).

Failure: MLE (Memory Limit Exceeded): DP table too large. Use space optimization (rolling array, variables).

Failure: Wrong Answer: Recurrence incorrect. Verify with hand example. Check base cases.

Failure: Stack Overflow: Recursion depth too deep. Switch to tabulation or increase stack size.

Failure: Integer Overflow: Intermediate values exceed int range. Use long or BigInteger.

DP Problem Classification Chart

By dimension:

• 1D DP: Single sequence/array. Example: Climbing Stairs, House Robber, Coin Change, LIS.
• 2D DP: Two sequences or 2D grid. Example: Edit Distance, LCS, Grid Paths, Longest Palindrome.
• 3D DP: Three independent parameters. Example: Stock with k transactions, Burst Balloons variants.

By optimization goal:

• Max/Min: Find extreme value. Example: Max profit, Min cost, Max length.
• Count: Count number of ways. Example: Unique paths, Number of ways to decode.
• Boolean: Reachability/existence. Example: Word break, Can partition.

By input type:

• Array/Sequence DP: Process elements in order. Example: Climbing Stairs, House Robber.
• String DP: Character-level processing. Example: Edit Distance, Word Break.
• Grid/2D DP: Coordinate-based. Example: Unique Paths, Min Path Sum.
• Interval DP: Subrange optimization. Example: Burst Balloons, Matrix Chain Multiplication.
• Knapsack DP: Selection under constraint. Example: 0/1 Knapsack, Coin Change.

Code Review: What Interviewers Look For

✓ Clear variable naming: "dp[i]" → "minCoinsToBuyAmount[i]". Be explicit.

✓ Correct base cases: Every DP solution must start correctly. Verify manually.

✓ Proper loop bounds: Off-by-one errors are common. Use i < n vs i <= n consistently.

✓ Efficient transitions: Recurrence should be O(1) per state if possible. Avoid nested loops inside transitions.

✓ Input validation: Handle null, empty, negative inputs gracefully.

✓ Complexity analysis: State the time and space complexity clearly.

✓ Readability: Comments on the recurrence logic. Code should be understandable without explanation.

✗ Overly optimized code: Balance optimization with clarity. A slow but correct solution beats a fast but wrong one.

Learning Resources Organized by Level

Beginner: Start with 1D DP on single arrays (Climbing Stairs, House Robber). Implement both memoization and tabulation.

Intermediate: Move to 2D DP (Edit Distance, LCS). Solve knapsack variants. Understand space optimization.

Advanced: Tackle interval DP (Burst Balloons), state machines (Stock trading), bitmask DP (subset enumeration).

Expert: Study advanced optimization techniques (Convex Hull Trick, monotone queue DP, digit DP). Solve Codeforces rounds.

DP in Different Languages

C++: Use vector<int> or array. Unordered_map for memoization. Fast execution.

Python: Use list or dict. @lru_cache decorator for automatic memoization. Great for prototyping.

Java: Use int[] or HashMap. Verbose but safe type system. Good for large-scale systems.

C#: Dictionary<K,V> for memoization, int[] for tabulation. Similar to Java.

JavaScript: Use Map or object. Flexible but beware of performance on large inputs.

Final Practice Recommendation

Solve at least 2-3 problems from each category (1D, 2D, knapsack, string, interval, state machine). Aim for fluency: able to code solution in 20 minutes without reference. After mastery, continue solving new problems—DP patterns keep surprising even experts!