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
110
111
112
113

# === ERROR 1: Missing Base Case ===
 
# BUGGY: No base case for empty string
def count_substrings_buggy(s: str) -> int:
    """Count all possible substrings."""
    if len(s) == 1:  # Only one base case
        return 1
    
    # BUG: What if s is empty? This will call count_substrings("") which
    # doesn't match len(s) == 1, leads to index errors or infinite recursion
    return len(s) + count_substrings_buggy(s[1:])
 
# CORRECT: Handle all minimal cases
def count_substrings_correct(s: str) -> int:
    if len(s) == 0:  # MISSING BASE CASE added
        return 0
    if len(s) == 1:
        return 1
    return len(s) + count_substrings_correct(s[1:])
 
 
# === ERROR 2: Wrong Base Value ===
 
# BUGGY: Wrong base case for Fibonacci
def fibonacci_buggy(n: int) -> int:
    if n <= 0:
        return 0
    if n == 1:
        return 0  # BUG: fib(1) should be 1, not 0!
    return fibonacci_buggy(n - 1) + fibonacci_buggy(n - 2)
 
# Test: fib(2) = fib(1) + fib(0) = 0 + 0 = 0 (should be 1!)
# All Fibonacci numbers will be wrong.
 
# CORRECT: Proper Fibonacci base cases
def fibonacci_correct(n: int) -> int:
    if n <= 0:
        return 0  # fib(0) = 0
    if n == 1:
        return 1  # fib(1) = 1
    return fibonacci_correct(n - 1) + fibonacci_correct(n - 2)
 
 
# === ERROR 3: Inconsistent Base with Recurrence ===
 
# Recurrence: dp[i] represents min cost to reach step i from step 0
# dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
 
# BUGGY: Base case doesn't match recurrence semantics
def min_cost_climbing_buggy(cost: list) -> int:
    n = len(cost)
    dp = [0] * (n + 1)
    
    dp[0] = cost[0]  # BUG: dp[0] should be 0 (no cost to be at step 0)
    dp[1] = cost[1]  # BUG: dp[1] should consider coming from step 0
    
    for i in range(2, n + 1):
        dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
    
    return dp[n]  # Wrong answer due to wrong base cases
 
# CORRECT: Base cases match recurrence semantics
def min_cost_climbing_correct(cost: list) -> int:
    n = len(cost)
    dp = [0] * (n + 1)
    
    # dp[i] = minimum cost to reach step i
    # You start on step 0 or step 1 with no prior cost
    dp[0] = 0  # Cost to be at step 0 before any move
    dp[1] = 0  # Cost to be at step 1 before any move (can start here)
    
    for i in range(2, n + 1):
        # To reach step i: come from i-1 (pay cost[i-1]) or i-2 (pay cost[i-2])
        dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
    
    return dp[n]
 
 
# === ERROR 4: Off-by-One in Base Case Index ===
 
# Problem: Compute number of ways to climb n stairs (1 or 2 steps at a time)
 
# BUGGY: Base case indexing mismatch
def climb_stairs_buggy(n: int) -> int:
    if n <= 0:
        return 0  # BUG: What does this mean?
    
    dp = [0] * (n + 1)
    dp[0] = 0  # BUG: There IS one way to stay at step 0 (do nothing)
    dp[1] = 1
    # dp[2] = dp[1] + dp[0] = 1 + 0 = 1 (should be 2!)
    
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]  # Wrong!
 
# CORRECT: Think about what dp[i] means
def climb_stairs_correct(n: int) -> int:
    if n <= 0:
        return 0 if n < 0 else 1  # 1 way to climb 0 stairs: do nothing
    
    dp = [0] * (n + 1)
    
    # dp[i] = number of ways to reach step i
    dp[0] = 1  # One way to be at step 0: start there
    dp[1] = 1  # One way to reach step 1: take one step
    # dp[2] = dp[1] + dp[0] = 1 + 1 = 2 (1+1 or 2) ✓
    
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

# === EXAMPLE: Designing Base Cases for Coin Change ===
 
# PROBLEM: Find minimum number of coins to make amount.
# If impossible, return -1.
 
# STEP 1: Define precisely what we compute
# dp[amount] = minimum number of coins needed to make exactly 'amount'
# If impossible, dp[amount] = infinity (or some sentinel)
 
# STEP 2: Identify smallest valid inputs
# Smallest amount: 0
# What about negative amounts? Invalid input, handle separately.
 
# STEP 3: Compute by definition
# dp[0] = 0 (zero coins needed to make amount 0)
# This is THE key insight many miss!
 
# STEP 4: Define recurrence
# dp[i] = min(dp[i - coin] + 1) for all coins where i >= coin
# Verify: dp[5] with coins=[1,2,5]
#   = min(dp[4] + 1, dp[3] + 1, dp[0] + 1)
#   = min(dp[4] + 1, dp[3] + 1, 0 + 1)
#   = uses dp[0] = 0 correctly ✓
 
def coin_change_correct(coins: list, amount: int) -> int:
    """Minimum coins to make amount."""
    INF = float('inf')
    
    # dp[i] = minimum coins to make exactly i
    dp = [INF] * (amount + 1)
    
    # BASE CASE: 0 coins needed for amount 0
    dp[0] = 0
    
    # Fill DP table
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] != INF:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != INF else -1
 
 
# === EXAMPLE: Designing Base Cases for Longest Common Subsequence ===
 
# PROBLEM: Find length of longest common subsequence of two strings.
 
# STEP 1: Define precisely
# dp[i][j] = length of LCS of text1[0:i] and text2[0:j]
# Note: 0:i means first i characters (indices 0 to i-1)
 
# STEP 2: Smallest valid inputs
# i = 0: text1[0:0] is empty string
# j = 0: text2[0:0] is empty string
 
# STEP 3: Compute by definition
# dp[0][j] = LCS of "" and text2[0:j] = 0 (nothing in common with empty)
# dp[i][0] = LCS of text1[0:i] and "" = 0 (nothing in common with empty)
 
# STEP 4: Define recurrence (for i, j > 0)
# If text1[i-1] == text2[j-1]:  (last chars match)
#     dp[i][j] = dp[i-1][j-1] + 1
# Else:
#     dp[i][j] = max(dp[i-1][j], dp[i][j-1])
 
def lcs_correct(text1: str, text2: str) -> int:
    """Length of longest common subsequence."""
    m, n = len(text1), len(text2)
    
    # dp[i][j] = LCS length of text1[0:i] and text2[0:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # BASE CASES: First row and first column are all 0
    # Already initialized by [[0] * (n+1) for ...]
    # dp[0][j] = 0 for all j (empty text1)
    # dp[i][0] = 0 for all i (empty text2)
    
    # Fill table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    return dp[m][n]
 
 
# === EXAMPLE: Designing Base Cases for Binary Search Tree Count ===
 
# PROBLEM: Count number of structurally unique BSTs with n nodes (values 1 to n)
# This is the nth Catalan number.
 
# STEP 1: Define precisely
# dp[n] = number of unique BSTs with n nodes
 
# STEP 2: Smallest valid inputs
# n = 0: No nodes
# n = 1: Single node
 
# STEP 3: Compute by definition
# dp[0] = 1 (ONE empty tree - this is the tricky one!)
#         The empty tree is a valid BST structure.
#         This is necessary for the recurrence to work.
# dp[1] = 1 (one tree with just the root)
 
# STEP 4: Recurrence
# For n nodes with root value k (1 <= k <= n):
#   Left subtree: k-1 nodes (values 1 to k-1)
#   Right subtree: n-k nodes (values k+1 to n)
#   dp[n] = sum(dp[k-1] * dp[n-k]) for k = 1 to n
 
# Verify: dp[2] = dp[0]*dp[1] + dp[1]*dp[0] = 1*1 + 1*1 = 2 ✓
# (Either root is 1 with right child 2, or root is 2 with left child 1)
 
def num_trees_correct(n: int) -> int:
    """Count unique BSTs with n nodes."""
    dp = [0] * (n + 1)
    
    # BASE CASES
    dp[0] = 1  # Empty tree (crucial for recurrence!)
    dp[1] = 1  # Single node tree
    
    for nodes in range(2, n + 1):
        for root in range(1, nodes + 1):
            left_subtrees = dp[root - 1]      # nodes in left subtree
            right_subtrees = dp[nodes - root]  # nodes in right subtree
            dp[nodes] += left_subtrees * right_subtrees
    
    return dp[n]

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

# === VERIFICATION BY MANUAL TRACE ===
 
def verify_climb_stairs():
    """
    Verify climb stairs base cases by manual computation.
    
    dp[n] = number of ways to climb n stairs (1 or 2 steps at a time)
    Recurrence: dp[n] = dp[n-1] + dp[n-2]
    """
    
    # Our base cases:
    dp_0 = 1  # 1 way to climb 0 stairs: do nothing
    dp_1 = 1  # 1 way to climb 1 stair: take one step
    
    # Manual verification of non-base cases:
    # dp[2] = dp[1] + dp[0] = 1 + 1 = 2
    # Expected: 2 ways (1+1 or 2)
    assert dp_1 + dp_0 == 2, "dp[2] is wrong!"
    
    # dp[3] = dp[2] + dp[1] = 2 + 1 = 3
    # Expected: 3 ways (1+1+1, 1+2, 2+1)
    dp_2 = 2
    assert dp_2 + dp_1 == 3, "dp[3] is wrong!"
    
    # dp[4] = dp[3] + dp[2] = 3 + 2 = 5
    # Expected: 5 ways (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)
    dp_3 = 3
    assert dp_3 + dp_2 == 5, "dp[4] is wrong!"
    
    print("Base cases verified!")
 
 
# === VERIFICATION BY KNOWN SEQUENCES ===
 
def verify_fibonacci_base():
    """Verify Fibonacci base cases against known sequence."""
    known_fib = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
    
    def fib(n):
        if n <= 0:
            return 0
        if n == 1:
            return 1
        return fib(n - 1) + fib(n - 2)
    
    for i, expected in enumerate(known_fib):
        computed = fib(i)
        assert computed == expected, f"fib({i}) = {computed}, expected {expected}"
    
    print("Fibonacci base cases verified!")
 
 
# === VERIFICATION BY EDGE CASES ===
 
def verify_coin_change_base():
    """Verify coin change handles edge cases correctly."""
    
    def coin_change(coins, amount):
        INF = float('inf')
        dp = [INF] * (amount + 1)
        dp[0] = 0  # Base case
        
        for i in range(1, amount + 1):
            for coin in coins:
                if coin <= i and dp[i - coin] != INF:
                    dp[i] = min(dp[i], dp[i - coin] + 1)
        
        return dp[amount] if dp[amount] != INF else -1
    
    # Edge case 1: amount = 0
    assert coin_change([1, 2, 5], 0) == 0, "0 coins for amount 0"
    
    # Edge case 2: single coin equals amount
    assert coin_change([5], 5) == 1, "one coin for exact amount"
    
    # Edge case 3: impossible amount
    assert coin_change([2], 3) == -1, "impossible with only 2s"
    
    # Edge case 4: empty coins (any positive amount impossible)
    assert coin_change([], 5) == -1, "impossible with no coins"
    assert coin_change([], 0) == 0, "0 coins for amount 0, even with no coins"
    
    print("Coin change base cases verified!")
 
 
# Run verifications
verify_climb_stairs()
verify_fibonacci_base()
verify_coin_change_base()

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

# === COUNTING WAYS: dp[0] = 1 ===
 
def unique_paths(m: int, n: int) -> int:
    """Count paths in m×n grid from top-left to bottom-right."""
    dp = [[1] * n for _ in range(m)]  # First row and column: 1 way each
    
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m-1][n-1]
 
 
def count_subsets_with_sum(nums: list, target: int) -> int:
    """Count subsets that sum to target."""
    dp = [0] * (target + 1)
    dp[0] = 1  # ONE way to make sum 0: empty subset
    
    for num in nums:
        for s in range(target, num - 1, -1):
            dp[s] += dp[s - num]
    
    return dp[target]
 
 
# === FINDING MINIMUM: dp[0] = 0, others = infinity ===
 
def min_jumps_to_end(nums: list) -> int:
    """Minimum jumps to reach end of array."""
    n = len(nums)
    INF = float('inf')
    
    dp = [INF] * n
    dp[0] = 0  # 0 jumps to reach position 0
    
    for i in range(n):
        if dp[i] == INF:
            continue
        for j in range(1, nums[i] + 1):
            if i + j < n:
                dp[i + j] = min(dp[i + j], dp[i] + 1)
    
    return dp[n-1] if dp[n-1] != INF else -1
 
 
# === STRING DP: Initialize entire row/column ===
 
def is_interleaving(s1: str, s2: str, s3: str) -> bool:
    """Check if s3 is interleaving of s1 and s2."""
    m, n = len(s1), len(s2)
    if m + n != len(s3):
        return False
    
    # dp[i][j] = True if s3[0:i+j] is interleaving of s1[0:i] and s2[0:j]
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    
    # BASE CASE: dp[0][0] = True (empty matches empty)
    dp[0][0] = True
    
    # BASE CASE: First column (using only s1)
    for i in range(1, m + 1):
        dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
    
    # BASE CASE: First row (using only s2)
    for j in range(1, n + 1):
        dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
    
    # Fill rest
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or \
                       (dp[i][j-1] and s2[j-1] == s3[i+j-1])
    
    return dp[m][n]
 
 
# === TREE RECURSION: Handle None ===
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def max_path_sum(root: TreeNode) -> int:
    """Maximum path sum in binary tree."""
    result = [float('-inf')]  # Track global maximum
    
    def max_gain(node: TreeNode) -> int:
        # BASE CASE: empty node contributes nothing
        if node is None:
            return 0
        
        # Recursive: max gain from left and right subtrees
        left_gain = max(max_gain(node.left), 0)  # Ignore negative paths
        right_gain = max(max_gain(node.right), 0)
        
        # Update global max: path through current node
        result[0] = max(result[0], node.val + left_gain + right_gain)
        
        # Return max gain if we continue upward (can only use one branch)
        return node.val + max(left_gain, right_gain)
    
    max_gain(root)
    return result[0]

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

def debug_dp_with_base_case_check(func, *args):
    """
    Wrapper to debug DP functions by printing state.
    """
    import functools
    
    # Store all computed values
    computed = {}
    
    @functools.wraps(func)
    def wrapper(*inner_args):
        result = func(*inner_args)
        computed[inner_args] = result
        return result
    
    # Run the function
    final_result = wrapper(*args)
    
    # Print analysis
    print("=== Base Case Analysis ===")
    print(f"All computed states: {len(computed)}")
    
    # Find minimal keys (potential base cases)
    sorted_keys = sorted(computed.keys(), key=lambda x: sum(x) if isinstance(x, tuple) else x)
    print(f"Smallest states (likely base cases):")
    for key in sorted_keys[:5]:
        print(f"  {key} -> {computed[key]}")
    
    return final_result
 
 
# Example debugging session
 
def coin_change_debug(coins: list, amount: int) -> int:
    """Version with debugging output."""
    INF = float('inf')
    dp = [INF] * (amount + 1)
    dp[0] = 0
    
    print(f"Initial state: dp[0:5] = {dp[:min(5, amount+1)]}")
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] != INF:
                old_val = dp[i]
                dp[i] = min(dp[i], dp[i - coin] + 1)
                if old_val != dp[i]:
                    print(f"  dp[{i}] updated: {old_val} -> {dp[i]} (used coin {coin})")
    
    print(f"Final state: dp = {dp}")
    return dp[amount] if dp[amount] != INF else -1
 
 
# Test with debugging
print("\n=== Debug Run ===")
result = coin_change_debug([1, 2, 5], 6)
print(f"Result: {result}")
 
# Expected output shows:
# - dp[0] = 0 (base case)
# - Each transition building on base case
# - Final answer traceable back to dp[0]