Memoization

1. 1.Fibonacci Number
   Basic Top-Down memoization: memo[n] caches fib(n-1) + fib(n-2)easy
2. 2.Climbing Stairs
   1D Memoization: memo[i] = solve(i+1) + solve(i+2)easy
3. 3.House Robber
   Take vs Skip: memo[i] = max(solve(i+1), nums[i] + solve(i+2))medium
4. 4.Coin Change
   Unbounded memo: memo[amount] = 1 + min(solve(amount - coin))medium
5. 5.Word Break
   Suffix Memoization: memo[start] = boolean canSegment(s[start:])medium
6. 6.Decode Ways
   String Memoization: memo[i] = solve(i+1) + solve(i+2)medium
7. 7.Unique Paths
   Grid Memoization: memo[r][c] = solve(r+1,c) + solve(r,c+1)medium
8. 8.Minimum Path Sum
   Grid Memoization: memo[r][c] = grid[r][c] + min(down, right)medium
9. 9.Longest Common Subsequence
   2D Memo key (i, j): match -> 1 + solve(i+1, j+1), else max(down, right)medium
10. 10.Edit Distance
    2D Memo key (i, j): 1 + min(insert, delete, replace)medium
11. 11.Partition Equal Subset Sum
    2D State memo[i][target]: Take vs Skip item imedium
12. 12.Target Sum
    State (index, currentSum) converted to positive offset memomedium
13. 13.Longest Increasing Subsequence
    Memo key (index, prevIndex) or 1D suffix memo[i]medium
14. 14.Combination Sum IV
    Unbounded memo[target] = sum(solve(target - coin))medium
15. 15.Perfect Squares
    Unbounded memo[n] = 1 + min(solve(n - s*s))medium
16. 16.Interleaving String
    2D Memo key (i, j): checks prefix match of s1[i:] and s2[j:] with s3medium
17. 17.Longest Palindromic Subsequence
    Substring Memo key (i, j): match -> 2 + solve(i+1, j-1)medium
18. 18.House Robber III
    Tree Memo: postorder DFS with memoization or (rob, skip) tuplemedium
19. 19.Longest Increasing Path in a Matrix
    DFS + Memo: memo[r][c] = 1 + max(dfs(neighbors))hard
20. 20.Different Ways to Add Parentheses
    Expression Divide & Conquer + string memoizationmedium

1. 21.Burst Balloons
   Interval Memo key (left, right): try last balloon k burst in rangehard
2. 22.Stone Game
   Game Theory Memo key (i, j): max score difference between playersmedium
3. 23.Regular Expression Matching
   2D Memo key (i, j) for text i and pattern j with . and *hard
4. 24.Distinct Subsequences
   String Memo key (i, j): count ways to match target subsequencehard
5. 25.Dungeon Game
   Reverse Grid Memo: memo[r][c] = min health required at (r, c)hard
6. 26.Scramble String
   3D Memo or string key (s1, s2): recursive split comparisonhard
7. 27.Palindrome Partitioning variants
   Memo key (start): min cuts or valid partition listsmedium
8. 28.DP on Trees
   DFS + Memoization caching subtree state queriesmedium
9. 29.DFS + Memoization on DAG
   Topological order implicit via DFS memoization on DAG nodesmedium
10. 30.Bitmask DP with Memoization
    State (node, mask): memoization over subset bitmaskshard

1. Recursive solution works but is too slow?Memoization
2. Same function arguments appear again?Cache that state
3. Need Top-Down DP?Recursion + Memo
4. State has multiple variables?Struct / Matrix Key
5. Need to skip invalid / duplicate states?Lookup ok in memo

package main

import "fmt"

// Multi-variable state struct (comparable type for Go map keys)
type StateKey struct {
    Index    int
    Capacity int
}

func knapsackMemo(weights, values []int, index, capacity int, memo map[StateKey]int64) int64 {
    // 1. Base Case
    if index < 0 || capacity <= 0 {
        return 0
    }

    // 2. Cache Check (Lookup ok in memo map)
    key := StateKey{Index: index, Capacity: capacity}
    if val, ok := memo[key]; ok {
        return val // CACHE HIT!
    }

    // 3. Solve Smaller States
    skip := knapsackMemo(weights, values, index-1, capacity, memo)
    var take int64 = 0
    if weights[index] <= capacity {
        take = int64(values[index]) + knapsackMemo(weights, values, index-1, capacity-weights[index], memo)
    }

    best := skip
    if take > skip {
        best = take
    }

    // 4. Store in Cache & Return
    memo[key] = best
    return best
}

func main() {
    weights := []int{2, 3, 4, 5}
    values := []int{3, 4, 5, 6}
    memo := make(map[StateKey]int64)

    maxVal := knapsackMemo(weights, values, len(weights)-1, 5, memo)
    fmt.Println("Max Knapsack Value:", maxVal) // Output: 7
}

Core Memoization Pattern

Base Case → Cache Check → Solve → Store → Return
Memo Key = Complete State (All changing variables)
Visited Array (Boolean) ≠ Memoized Result (Computed Value)
Time Complexity = Unique States × Work per State
Space Complexity = Memo Storage + Recursion Stack Depth

Memoization Variants & Applications

Common Interview Mistakes

• • Memoizing with an incomplete state key (e.g. storing memo[index] when capacity or stock status changes future choices).
• • Forgetting to store the result in the memo cache before returning (leaving plain exponential recursion intact).
• • Using 0 as an uninitialized sentinel when 0 is a valid computed answer (use map lookup ok or -1 sentinel instead).
• • Caching only successful branches and failing to memoize failed states (false/negative results repeat often too).
• • Confusing boolean visited arrays (cycle prevention) with computed memoization state caches.
• • Ignoring recursion stack depth limits (extremely deep recursions may require bottom-up tabulation).
• • Using non-comparable Go slice types directly as map keys instead of structs or integer bitmasks.
• • Mutating global state inside recursive calls that invalidates cached state assumptions.

Interview Rules

Recursion repeats work → Memoization (Top-Down DP)
Rule 1                → Define state parameters completely
Rule 2                → Check cache before recursive work
Rule 3                → Store computed answer before returning
Rule 4                → Cache both success and failure results
Rule 5                → In Go, use structs or matrices for multi-var keys
Time Complexity       → Unique States × Transitions per State
Space Complexity      → Memo Storage + Call Stack Depth

💡 Golden Rule: If the same recursive state appears again, don't solve it again—return the answer you already stored.

Top-Down DP = Recursion + Memo Cache
Golden Order: Base Case → Memo Hit → Solve → Store → Return
Include ALL changing parameters in state key
Cache failed states (false / -1) as well as success states
Map lookup: val, ok := memo[key]
Time: States × Work Per State
Space: Memo Size + Stack Depth