Dynamic Programming

1. 1.Climbing Stairs
   1D DP: ways[i] = ways[i-1] + ways[i-2]easy
2. 2.House Robber
   Take vs Skip: max(dp[i-1], nums[i] + dp[i-2])medium
3. 3.House Robber II
   Circular array: rob 0..n-2 or 1..n-1medium
4. 4.Coin Change
   Unbounded Knapsack min coins: min(dp[w], 1 + dp[w-coin])medium
5. 5.Coin Change II
   Unbounded combinations: dp[w] += dp[w-coin]medium
6. 6.Maximum Product Subarray
   Track both maxProduct and minProduct due to negative flipsmedium
7. 7.Longest Increasing Subsequence
   dp[i] = max(dp[j] + 1) for j < i or O(n log n) patience sortmedium
8. 8.Longest Common Subsequence
   2D String DP: match -> 1 + dp[i-1][j-1], else max(top, left)medium
9. 9.Word Break
   Partition DP: dp[i] = true if dp[j] && wordDict.contains(s[j:i])medium
10. 10.Decode Ways
    1D string DP: 1 digit valid + 2 digit valid (10..26)medium
11. 11.Unique Paths
    Grid DP: dp[r][c] = dp[r-1][c] + dp[r][c-1]medium
12. 12.Minimum Path Sum
    Grid DP: dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])medium
13. 13.Partition Equal Subset Sum
    0/1 Knapsack: find subset sum target = sum/2medium
14. 14.Target Sum
    0/1 Knapsack subset sum transformation: P = (sum + target) / 2medium
15. 15.0/1 Knapsack
    Take vs Skip: iterate capacity right-to-left in 1D arraymedium
16. 16.Edit Distance
    2D String DP: insert, delete, or replace operationsmedium
17. 17.Palindromic Substrings
    Expand around center or 2D substring DP dp[i][j]medium
18. 18.Longest Palindromic Subsequence
    Subsequence DP: match -> 2 + dp[i+1][j-1], else max(dp[i+1][j], dp[i][j-1])medium
19. 19.Best Time to Buy and Sell Stock with Cooldown
    State Machine DP: states = (hold, sold, reset)medium
20. 20.Best Time to Buy and Sell Stock III
    State Machine DP: 2 transactions limit, 4 variableshard
21. 21.Dungeon Game
    Reverse Grid DP: compute min health required from bottom-right to top-lefthard
22. 22.Interleaving String
    2D String DP: dp[i][j] checks prefix matches of s1 and s2 with s3medium
23. 23.Distinct Subsequences
    String DP counting: match -> dp[i-1][j-1] + dp[i-1][j]hard
24. 24.Burst Balloons
    Interval / Matrix Chain DP: last balloon burst k in range (i, j)hard
25. 25.House Robber III
    Tree DP: postorder DFS returns (robCurrent, skipCurrent)medium

1. 26.Fibonacci Number
   Base DP: dp[i] = dp[i-1] + dp[i-2] with O(1) spaceeasy
2. 27.Min Cost Climbing Stairs
   1D DP: dp[i] = cost[i] + min(dp[i-1], dp[i-2])easy
3. 28.Combination Sum IV
   Unbounded Knapsack permutations: loop capacity first, then itemsmedium
4. 29.Perfect Squares
   Unbounded Knapsack min items: dp[i] = min(dp[i], 1 + dp[i - s*s])medium
5. 30.Triangle
   Grid DP: bottom-up accumulation dp[i][j] += min(dp[i+1][j], dp[i+1][j+1])medium
6. 31.Maximal Square
   2D Grid DP: dp[r][c] = 1 + min(top, left, diagonal) for 1smedium
7. 32.Longest Palindromic Substring
   Substring DP or expand around center in O(n^2)medium
8. 33.Regular Expression Matching
   2D String Matching with . and * wildcardshard
9. 34.Wildcard Matching
   2D String Matching with ? and * wildcardshard
10. 35.Minimum Falling Path Sum
    Grid DP: dp[r][c] = cell + min(left, center, right)medium
11. 36.Cherry Pickup
    Grid DP with 2 simultaneous paths: dp[r1][c1][r2]hard
12. 37.Stone Game
    Interval Game DP: max difference dp[i][j] = max(piles[i]-dp[i+1][j], piles[j]-dp[i][j-1])medium
13. 38.Delete and Earn
    Transform frequency sum to House Robber patternmedium
14. 39.Integer Break
    Math / DP: max product dp[i] = max(j * (i-j), j * dp[i-j])medium
15. 40.Maximum Length of Repeated Subarray
    2D Continuous Subarray DP: match -> 1 + dp[i+1][j+1]medium

1. Same smaller problem repeating?Dynamic Programming
2. Can I describe the problem with a state?dp[state] = answer
3. Does current answer depend on previous states?Transition
4. Recursive solution repeats work?Memoization (Top-Down)
5. Can I compute states in dependency order?Tabulation (Bottom-Up)
6. Take current item or skip current item?Take / Skip Pattern
7. Two strings comparison or alignment?dp[i][j]
8. Grid reachability or minimum cost path?dp[r][c]

package main

import "fmt"

// Top-Down Memoization with int64 overflow protection
func coinChangeMemo(coins []int, amount int, memo map[int]int64) int64 {
    if amount == 0 {
        return 0
    }
    if amount < 0 {
        return -1
    }
    if val, exists := memo[amount]; exists {
        return val
    }

    var minCoins int64 = 1e18 // Use large int64 sentinel to prevent overflow
    for _, coin := range coins {
        res := coinChangeMemo(coins, amount-coin, memo)
        if res >= 0 && res+1 < minCoins {
            minCoins = res + 1
        }
    }

    if minCoins == 1e18 {
        memo[amount] = -1
    } else {
        memo[amount] = minCoins
    }
    return memo[amount]
}

// Bottom-Up Tabulation with Space Optimization O(1) space
func robTabulation(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    var prev2, prev1 int = 0, 0
    for _, num := range nums {
        // Core invariant: current best = max(skip current, rob current + best 2 houses back)
        take := num + prev2
        skip := prev1
        current := take
        if skip > take {
            current = skip
        }
        prev2 = prev1
        prev1 = current
    }
    return prev1
}

func main() {
    memo := make(map[int]int64)
    fmt.Println("Min Coins:", coinChangeMemo([]int{1, 2, 5}, 11, memo)) // 3
    fmt.Println("Max Robbed:", robTabulation([]int{2, 7, 9, 3, 1}))    // 12
}

Core DP Patterns & Mechanics

Repeated subproblems → Store & reuse state
Take / Skip decision → dp[i] = opt(dp[i-1], val + dp[i-2])
0/1 Knapsack 1D table → Iterate capacity right to left
Unbounded Knapsack 1D → Iterate capacity left to right
2D String Matching → dp[i][j] diagonal match or top/left max
Time Complexity → Number of States × Work per State

DP Families & Variants

Common Interview Mistakes

• • Coding before clearly defining what dp[state] means in plain language.
• • Leaving necessary constraint variables out of the state definition (e.g. remaining capacity, holding stock, or transaction count).
• • Using the wrong loop direction in 1D Knapsack (updating left-to-right in 0/1 Knapsack accidentally reuses items multiple times).
• • Incorrect base cases or failing to initialize unreachable states to infinity or negative infinity.
• • Integer overflow when counting total combinations or paths (forgetting int64 guards or modulo arithmetic).
• • Optimizing space to O(1) or O(N) prematurely before getting the full multi-dimensional DP table logic correct.
• • Confusing continuous subarrays (contiguous elements) with non-continuous subsequences (can skip elements).

Interview Rules

Repeated Subproblems → Dynamic Programming
Step 1              → Define dp[state] meaning explicitly
Step 2              → Identify decision choices (Take vs Skip)
Step 3              → Formulate transition equation
Step 4              → Set boundary base cases
0/1 Knapsack 1D     → Right-to-Left capacity loop
Unbounded 1D        → Left-to-Right capacity loop
2D String Matching  → Matrix dp[i][j]
Time Complexity     → Total States × Work per State
Space Optimization  → Optimize array dimensions after correctness

💡 Golden Rule: Define exactly what one DP state means, then express that state using smaller already-solved states.

Identify repeating subproblems
Define dp[state] cell meaning
Formulate state transition formula
Establish correct base cases
Top-Down (Memoization) or Bottom-Up (Tabulation)
Check loop direction for 1D Knapsack tables
Verify bounds and avoid integer overflow