Dynamic Programming — DSA Mastery

Fibonacci — DP Table Fill

n =

dp[] array (index = n):

Press Animate Fill to see bottom-up DP in action.

Coin Change — 2D DP Table

Coins: [1, 3, 4]. Find minimum coins for each amount 0→8. Each cell = min(dp[amt-coin]+1) for each valid coin.

Press Fill Table to see the DP grid built step by step.

6 Core DP Patterns

Pattern	State	Key Problems
1D Linear	dp[i]	Fibonacci, Climbing Stairs, House Robber
2D Grid	dp[i][j]	Unique Paths, Minimum Path Sum
String/Sequence	dp[i][j] = substr	LCS, Edit Distance, LPS
Knapsack	dp[i][w] = value	0/1 Knapsack, Partition Equal Subset
Interval	dp[i][j] = range	Burst Balloons, Matrix Chain
State Machine	dp[state]	Best Time to Buy/Sell Stock

Is It a DP Problem?

Overlapping Subproblems

The same smaller problem is solved multiple times. fib(5) needs fib(4) and fib(3). fib(4) also needs fib(3). → Cache it!

Optimal Substructure

Optimal solution = combination of optimal solutions to smaller problems. "The best way to reach step n = best way to reach step n-1 or n-2 + 1 step."

Signal words

"Minimum/maximum number of ways", "Count distinct ways", "Is it possible", "Longest/shortest sequence satisfying..."

Top-Down vs Bottom-Up

	Top-Down (Memo)	Bottom-Up (Tabulation)
Approach	Recursion + cache	Iteration + table fill
Space	O(n) call stack	O(n) or O(1) optimized
Intuitive?	Easier to write first	Harder to derive
Speed	Slightly slower	Faster (no recursion overhead)

Workflow

Start with recursive brute force → add memoization → convert to bottom-up tabulation → optimize space.

Top-Down vs Bottom-Up

# Top-down: recursion + @lru_cache
from functools import lru_cache

@lru_cache(maxsize=None)
def climb(n):
    if n <= 2: return n
    return climb(n-1) + climb(n-2)

# Bottom-up: fill table iteratively
def climb_bu(n):
    if n <= 2: return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# Space-optimized: O(1)
def climb_opt(n):
    a, b = 1, 2
    for _ in range(2, n):
        a, b = b, a + b
    return b

Coin Change + House Robber

# Coin Change — min coins
def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for amt in range(1, amount + 1):
        for coin in coins:
            if coin <= amt:
                dp[amt] = min(dp[amt], dp[amt - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

# House Robber
def rob(nums):
    prev2, prev1 = 0, 0
    for n in nums:
        curr = max(prev1, prev2 + n)
        prev2, prev1 = prev1, curr
    return prev1

# Longest Common Subsequence
def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    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] + 1
            else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

LeetCode Problems

EasyClimbing Stairs1D DP / Fibonacci
EasyMin Cost Climbing Stairs1D DP with cost
MediumHouse Robberdp[i] = max(dp[i-1], dp[i-2]+nums[i])
MediumCoin Changedp[amt] = min(dp[amt-coin]+1)
MediumLongest Common Subsequence2D string DP
MediumLongest Increasing Subsequencedp[i] = max subsequence ending at i
MediumUnique Paths2D grid DP
MediumPartition Equal Subset Sum0/1 Knapsack
HardEdit Distance2D string DP with 3 choices
HardBurst BalloonsInterval DP