Memoization — Top-Down Dynamic Programming

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

from functools import cache
 
# EXAMPLE 1: Catalan Numbers
# Natural recursive definition: C(n) = Σ C(i) * C(n-1-i) for i in [0, n-1]
# This is fundamentally recursive - the definition IS the recursion
 
@cache
def catalan(n: int) -> int:
    """
    The nth Catalan number.
    
    Counts: BST shapes, valid parentheses, polygon triangulations, etc.
    The definition is recursive, so top-down is the natural approach.
    """
    if n <= 1:
        return 1
    
    result = 0
    for i in range(n):
        result += catalan(i) * catalan(n - 1 - i)
    return result
 
 
# EXAMPLE 2: Subset Sum (Decision Tree)
# "Can we select items that sum to target?"
# Natural as: "Take first item and solve for (target - item), OR skip and solve for same target"
 
@cache
def subset_sum(nums: tuple, target: int, idx: int = 0) -> bool:
    """
    Can we select elements from nums[idx:] that sum to target?
    
    Decision tree: At each element, we can include it or exclude it.
    Top-down naturally models this binary choice structure.
    """
    if target == 0:
        return True  # Found a valid subset
    if target < 0 or idx >= len(nums):
        return False  # Invalid or exhausted
    
    # Decision: include nums[idx] OR exclude it
    include = subset_sum(nums, target - nums[idx], idx + 1)
    exclude = subset_sum(nums, target, idx + 1)
    
    return include or exclude
 
 
# EXAMPLE 3: Word Break (Suffix pattern)
# "Can s[i:] be segmented using dictionary words?"
# Naturally recursive: try each word starting at i, then solve s[i + len(word):]
 
@cache
def word_break(s: str, word_dict: frozenset, start: int = 0) -> bool:
    """
    Can s[start:] be broken into dictionary words?
    
    The suffix pattern: if we match word at start, 
    can we break s[start + len(word):]?
    """
    if start == len(s):
        return True  # Successfully broke entire string
    
    for end in range(start + 1, len(s) + 1):
        word = s[start:end]
        if word in word_dict and word_break(s, word_dict, end):
            return True
    
    return False
 
 
# Tests
print(f"Catalan(5) = {catalan(5)}")  # 42
print(f"subset_sum([3,1,5,9], 8) = {subset_sum((3,1,5,9), 8)}")  # True (3+5)
print(f"word_break('leetcode', {{'leet','code'}}) = "
      f"{word_break('leetcode', frozenset(['leet', 'code']))}")  # True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

# Example where lazy evaluation provides significant savings
 
# SPARSE DEPENDENCY: "Is there a path from (0,0) to (m-1, n-1) 
# avoiding obstacles, using only right/down moves?"
# If the target is blocked or unreachable, we don't need full grid
 
def grid_path_exists(grid: list[list[int]], memo: dict = None, 
                     i: int = 0, j: int = 0) -> bool:
    """
    Top-down: Only explores cells reachable from (i, j).
    If path exists, we find it without touching every cell.
    """
    if memo is None:
        memo = {}
    
    m, n = len(grid), len(grid[0])
    
    # Base cases
    if i >= m or j >= n or grid[i][j] == 1:  # 1 = obstacle
        return False
    if i == m - 1 and j == n - 1:
        return True  # Reached target!
    
    key = (i, j)
    if key in memo:
        return memo[key]
    
    # Try moving right or down
    result = (grid_path_exists(grid, memo, i + 1, j) or 
              grid_path_exists(grid, memo, i, j + 1))
    
    memo[key] = result
    return result
 
 
# For comparison, bottom-up must fill entire grid even if blocked
def grid_path_exists_bottomup(grid: list[list[int]]) -> bool:
    """
    Bottom-up: Must process every cell regardless of reachability.
    """
    m, n = len(grid), len(grid[0])
    dp = [[False] * n for _ in range(m)]
    
    # Must fill entire table
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            if grid[i][j] == 1:
                dp[i][j] = False
            elif i == m - 1 and j == n - 1:
                dp[i][j] = True
            else:
                down = dp[i + 1][j] if i + 1 < m else False
                right = dp[i][j + 1] if j + 1 < n else False
                dp[i][j] = down or right
    
    return dp[0][0]
 
 
# Example with early obstruction
grid = [
    [0, 1, 0, 0, 0],  # Obstacle at (0,1) blocks quick paths
    [0, 1, 0, 0, 0],  
    [0, 0, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0],
]
 
# Top-down will explore efficiently around obstacles
# Bottom-up fills all 25 cells regardless
 
 
# EARLY TERMINATION example: Find any valid partition
# (not count all partitions - just find one)
 
def can_partition(nums: list[int]) -> bool:
    """
    Can we partition nums into two equal-sum subsets?
    
    Top-down with early termination: Stop as soon as we find a valid partition.
    Bottom-up would compute all reachable sums.
    """
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    
    memo = {}
    
    def dp(idx: int, remaining: int) -> bool:
        if remaining == 0:
            return True  # Found valid partition - STOP HERE
        if idx >= len(nums) or remaining < 0:
            return False
        
        if (idx, remaining) in memo:
            return memo[(idx, remaining)]
        
        # IMPORTANT: Short-circuit OR - if first is True, don't check second
        result = dp(idx + 1, remaining - nums[idx]) or dp(idx + 1, remaining)
        
        memo[(idx, remaining)] = result
        return result
    
    return dp(0, target)
 
 
# When partition exists early, top-down stops immediately
# Bottom-up computes all (idx, sum) combinations
print(f"Can partition [1,5,11,5]: {can_partition([1, 5, 11, 5])}")  # True (1+5+5 = 11)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

from functools import cache
 
# EXAMPLE 1: Regular Expression Matching
# State: (text_index, pattern_index) - simple enough for arrays
# BUT the pattern with '*' creates complex branching that's cleaner recursively
 
@cache
def regex_match(s: str, p: str, i: int = 0, j: int = 0) -> bool:
    """
    Does pattern p match string s?
    '.' matches any single character
    '*' matches zero or more of the preceding element
    
    Top-down is natural because '*' creates complex case analysis.
    """
    # Pattern exhausted - success only if string also exhausted
    if j == len(p):
        return i == len(s)
    
    # Check if current characters match
    first_match = i < len(s) and (p[j] == s[i] or p[j] == '.')
    
    # Handle '*' - must be preceded by another character (j >= 1)
    if j + 1 < len(p) and p[j + 1] == '*':
        # Either skip the 'x*' pattern (zero occurrences)
        # Or consume one character and try again
        return (regex_match(s, p, i, j + 2) or  # Skip 'x*'
                (first_match and regex_match(s, p, i + 1, j)))  # Use 'x*' once
    
    # No '*' coming - just check current and continue
    return first_match and regex_match(s, p, i + 1, j + 1)
 
 
# EXAMPLE 2: Traveling Salesman (Bitmask DP)
# State: (current_city, visited_set as bitmask)
# Top-down lets us use the bitmask directly
 
@cache
def tsp(distances: tuple, current: int, visited: int, n: int) -> int:
    """
    Minimum cost to visit all cities starting from 'current',
    having already visited cities encoded in 'visited' bitmask.
    
    State: (current_city, visited_mask)
    Top-down because the state is naturally a bitmask, not array indices.
    """
    # All cities visited - return to start
    if visited == (1 << n) - 1:
        return distances[current][0]  # Return to city 0
    
    min_cost = float('inf')
    for next_city in range(n):
        if visited & (1 << next_city) == 0:  # Not yet visited
            new_visited = visited | (1 << next_city)
            cost = distances[current][next_city] + \
                   tsp(distances, next_city, new_visited, n)
            min_cost = min(min_cost, cost)
    
    return min_cost
 
 
# EXAMPLE 3: Scramble String (Complex String State)
# State: Two substrings being compared
# Very natural with recursion, awkward to tabulate
 
@cache
def is_scramble(s1: str, s2: str) -> bool:
    """
    Is s2 a 'scrambled' version of s1?
    (Can be obtained by recursively swapping children of binary split)
    
    State is essentially two strings - trivial to memoize with strings as keys,
    but would require complex indexing for tabulation.
    """
    if s1 == s2:
        return True
    if sorted(s1) != sorted(s2):
        return False
    if len(s1) <= 1:
        return s1 == s2
    
    n = len(s1)
    for i in range(1, n):
        # Try split at position i
        # Either halves aren't swapped, or they are
        if (is_scramble(s1[:i], s2[:i]) and is_scramble(s1[i:], s2[i:])) or \
           (is_scramble(s1[:i], s2[n-i:]) and is_scramble(s1[i:], s2[:n-i])):
            return True
    
    return False
 
 
# Tests
print(f"regex_match('mississippi', 'mis*is*p*.') = "
      f"{regex_match('mississippi', 'mis*is*p*.')}")  # False
 
distances = ((0, 10, 15, 20),
             (10, 0, 35, 25),
             (15, 35, 0, 30),
             (20, 25, 30, 0))
print(f"TSP minimum cost: {tsp(distances, 0, 1, 4)}")  # Start at 0, visited={0}
 
print(f"is_scramble('great', 'rgeat') = {is_scramble('great', 'rgeat')}")  # True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

"""
Comparison: Deriving Top-Down vs Bottom-Up for Edit Distance
=============================================================
 
Edit Distance: Minimum edits (insert, delete, replace) to transform s1 → s2
"""
 
# STEP 1: Plain recursion (the starting point for both approaches)
def edit_distance_recursive(s1: str, s2: str, i: int = None, j: int = None) -> int:
    """
    Plain recursive solution - easy to write from problem understanding.
    But has exponential time complexity due to overlapping subproblems.
    """
    if i is None:
        i, j = len(s1), len(s2)
    
    # Base cases
    if i == 0:
        return j  # Insert j characters
    if j == 0:
        return i  # Delete i characters
    
    # If last characters match, no operation needed
    if s1[i - 1] == s2[j - 1]:
        return edit_distance_recursive(s1, s2, i - 1, j - 1)
    
    # Try all three operations, take minimum
    return 1 + min(
        edit_distance_recursive(s1, s2, i, j - 1),      # Insert
        edit_distance_recursive(s1, s2, i - 1, j),      # Delete
        edit_distance_recursive(s1, s2, i - 1, j - 1),  # Replace
    )
 
 
# STEP 2A: Add memoization - TRIVIAL transformation
from functools import cache
 
@cache
def edit_distance_memoized(s1: str, s2: str, i: int = None, j: int = None) -> int:
    """
    Memoized version: Just add @cache decorator.
    That's literally the only change needed!
    
    (Note: We need to make i, j non-None defaults for caching to work properly)
    """
    if i is None:
        return edit_distance_memoized(s1, s2, len(s1), len(s2))
    
    if i == 0:
        return j
    if j == 0:
        return i
    
    if s1[i - 1] == s2[j - 1]:
        return edit_distance_memoized(s1, s2, i - 1, j - 1)
    
    return 1 + min(
        edit_distance_memoized(s1, s2, i, j - 1),
        edit_distance_memoized(s1, s2, i - 1, j),
        edit_distance_memoized(s1, s2, i - 1, j - 1),
    )
 
 
# STEP 2B: Convert to bottom-up - REQUIRES thinking about iteration order
def edit_distance_bottomup(s1: str, s2: str) -> int:
    """
    Bottom-up tabulation.
    
    Required additional decisions:
    1. Table dimensions: (len(s1) + 1) × (len(s2) + 1)
    2. Base case initialization: First row and column
    3. Iteration order: Row by row, left to right (or column by column)
    4. Access pattern: dp[i][j] depends on dp[i-1][j-1], dp[i-1][j], dp[i][j-1]
    """
    m, n = len(s1), len(s2)
    
    # Create table with proper dimensions
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Initialize base cases (first row and column)
    for i in range(m + 1):
        dp[i][0] = i  # Delete i characters
    for j in range(n + 1):
        dp[0][j] = j  # Insert j characters
    
    # Fill table in correct order
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i][j - 1],      # Insert
                    dp[i - 1][j],      # Delete
                    dp[i - 1][j - 1],  # Replace
                )
    
    return dp[m][n]
 
 
# Both give correct results
s1, s2 = "intention", "execution"
print(f"Edit distance '{s1}' → '{s2}':")
print(f"  Memoized: {edit_distance_memoized(s1, s2)}")
print(f"  Bottom-up: {edit_distance_bottomup(s1, s2)}")
# Both return 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

# EXAMPLE 1: Space Optimization with Rolling Array
# Edit distance with O(n) space instead of O(mn)
 
def edit_distance_optimized(s1: str, s2: str) -> int:
    """
    Bottom-up with space optimization.
    Since each row only depends on the previous row, keep only two rows.
    
    Space: O(min(m, n)) instead of O(m × n)
    This isn't possible with top-down memoization!
    """
    m, n = len(s1), len(s2)
    
    # Ensure s2 is the shorter string for better space usage
    if m < n:
        s1, s2 = s2, s1
        m, n = n, m
    
    # Only keep current and previous row
    prev = list(range(n + 1))
    curr = [0] * (n + 1)
    
    for i in range(1, m + 1):
        curr[0] = i
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(curr[j - 1], prev[j], prev[j - 1])
        prev, curr = curr, prev
    
    return prev[n]
 
 
# EXAMPLE 2: Fibonacci with O(1) space
# Only need last two values, not entire array
 
def fib_space_optimized(n: int) -> int:
    """
    O(1) space Fibonacci - impossible with memoization.
    """
    if n <= 1:
        return n
    
    prev2, prev1 = 0, 1
    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    
    return prev1
 
 
# EXAMPLE 3: LCS with solution reconstruction
# Bottom-up makes backtracking through the table easier
 
def lcs_with_reconstruction(s1: str, s2: str) -> tuple[int, str]:
    """
    Returns both length and the actual LCS string.
    Reconstruction is natural with bottom-up: trace back through the table.
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Fill table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    # Reconstruct by tracing back
    lcs = []
    i, j = m, n
    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            lcs.append(s1[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    
    return dp[m][n], ''.join(reversed(lcs))
 
 
# Tests
print(f"Edit distance optimized: {edit_distance_optimized('intention', 'execution')}")
print(f"Fib(100) O(1) space: {fib_space_optimized(100)}")
 
length, lcs = lcs_with_reconstruction("ABCBDAB", "BDCABA")
print(f"LCS length: {length}, LCS: '{lcs}'")