Learning

Dynamic Programming

Dynamic Programming

Overlapping Subproblems

python
# Naive Fibonacci — recomputes same subproblems! def fib_naive(n): if n <= 1: return n return fib_naive(n-1) + fib_naive(n-2) # fib(5) calls fib(3) twice, fib(2) three times!

Memoization (Top-Down)

python
def fib_memo(n, memo=None): if memo is None: memo = {} if n in memo: return memo[n] if n <= 1: return n memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo) return memo[n] # O(n) time, O(n) space

Tabulation (Bottom-Up)

python
def fib_tab(n): if n <= 1: return n dp = [0] * (n + 1) dp[1] = 1 for i in range(2, n + 1): dp[i] = dp[i-1] + dp[i-2] return dp[n] # O(n) time, O(n) space # Space-optimized: O(1) space def fib_optimized(n): if n <= 1: return n a, b = 0, 1 for _ in range(2, n + 1): a, b = b, a + b return b # O(n) time, O(1) space

0/1 Knapsack

python
def knapsack(weights, values, capacity): n = len(weights) dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): for w in range(capacity + 1): if weights[i-1] <= w: dp[i][w] = max( dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1] ) else: dp[i][w] = dp[i-1][w] return dp[n][capacity] print(knapsack([1,3,4,5], [1,4,5,7], 7)) # 9

Longest Common Subsequence

python
def lcs(text1, text2): m, n = len(text1), len(text2) dp = [[0] * (n + 1) for _ in range(m + 1)] 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] print(lcs('abcde', 'ace')) # 3 ('ace')

Coin Change

python
def coin_change(coins, amount): dp = [float('inf')] * (amount + 1) dp[0] = 0 for a in range(1, amount + 1): for coin in coins: if coin <= a: dp[a] = min(dp[a], dp[a - coin] + 1) return dp[amount] if dp[amount] != float('inf') else -1 print(coin_change([1, 2, 5], 11)) # 3 (5+5+1)

State Space Optimization

python
# Knapsack: 2D → 1D def knapsack_1d(weights, values, capacity): n = len(weights) dp = [0] * (capacity + 1) for i in range(n): for w in range(capacity, weights[i] - 1, -1): # Reverse! dp[w] = max(dp[w], dp[w - weights[i]] + values[i]) return dp[capacity] # LCS: 2D → 2 rows def lcs_optimized(text1, text2): m, n = len(text1), len(text2) prev = [0] * (n + 1) for i in range(1, m + 1): curr = [0] * (n + 1) for j in range(1, n + 1): if text1[i-1] == text2[j-1]: curr[j] = prev[j-1] + 1 else: curr[j] = max(prev[j], curr[j-1]) prev = curr return prev[n]
Key Rules
  • •DP applies when: (1) overlapping subproblems, (2) optimal substructure — optimal solution contains optimal sub-solutions
  • •Memoization (top-down): recursive + cache — easier to think about, may have stack overflow for deep recursion
  • •Tabulation (bottom-up): iterative table filling — no recursion limit, usually slightly faster
  • •0/1 Knapsack: dp[i][w] = max(not take item i, take item i) — each item used at most once
  • •Coin Change: dp[a] = min coins to make amount a — unbounded (each coin can be reused)
  • •2D → 1D optimization: iterate backwards for 0/1 knapsack (prevent using same item twice), forwards for unbounded
Your Task

Implement: 1) `fib_memo(n)` with memoization. 2) `fib_tab(n)` with tabulation and O(1) space variant. 3) `knapsack(weights, values, capacity)` with 2D DP. 4) `lcs(text1, text2)`. 5) `coin_change(coins, amount)`. 6) `climbing_stairs(n)` — count ways to reach top (1 or 2 steps at a time). Demonstrate all with clear input/output showing results.

EditorPython · JSX
PreviewUpdates on Run Tests
Loading preview…
Tests
Should implement fib_memo with lru_cache or manual memo
Should implement fib_tab iteratively
Should implement knapsack with 2D DP table
Should implement lcs with DP matrix
Should implement coin_change with DP
Should implement climbing_stairs