Dynamic Programming

// 4-Step DP Framework

1. Define: What does dp[i] represent?
2. Recurrence: How does dp[i] depend on previous states?
3. Base case: What are the trivially known values?
4. Build: Bottom-up iteration or top-down memoization.

Easy Climbing Stairs

INSIGHT: dp[i] = ways to reach step i = dp[i-1] + dp[i-2]. This is Fibonacci!

def climbStairs(n):
    if n <= 2: return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b
# O(n) time | O(1) space

Medium House Robber + House Robber II

INSIGHT: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Circular version: run linear twice (skip first OR skip last), take max.

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

# House Robber II (circular — first & last can't both be robbed)
def rob2(nums):
    if len(nums) == 1: return nums[0]
    def linear(houses):
        p2, p1 = 0, 0
        for n in houses:
            p2, p1 = p1, max(p1, p2 + n)
        return p1
    return max(linear(nums[:-1]), linear(nums[1:]))

Medium Coin Change

INSIGHT: dp[a] = min coins to make amount a. For each coin, dp[a] = min(dp[a], 1 + dp[a-coin]).

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if a - c >= 0:
                dp[a] = min(dp[a], 1 + dp[a - c])
    return dp[amount] if dp[amount] != float('inf') else -1
# Time: O(amount * coins) | Space: O(amount)

Medium Longest Increasing Subsequence

INSIGHT: O(n log n) uses patience sorting: maintain a list where each element is the smallest tail of IS with that length. Binary search to find where to place/replace.

# O(n²) DP
def lengthOfLIS_dp(nums):
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# O(n log n) Patience Sorting
import bisect
def lengthOfLIS(nums):
    sub = []  # sub[i] = smallest tail of IS with length i+1
    for n in nums:
        pos = bisect.bisect_left(sub, n)
        if pos == len(sub): sub.append(n)
        else: sub[pos] = n  # replace to keep smallest tails
    return len(sub)

Medium Word Break

def wordBreak(s, wordDict):
    word_set = set(wordDict)
    dp = [False] * (len(s) + 1)
    dp[0] = True   # empty prefix is always segmentable
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    return dp[len(s)]

// 2D DP Essentials

Unique Paths — O(m·n)

def uniquePaths(m, n):
    dp = [[1] * n for _ in range(m)]
    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = dp[r-1][c] + dp[r][c-1]
    return dp[m-1][n-1]

Longest Common Subsequence — O(m·n)

def longestCommonSubsequence(t1, t2):
    dp = [[0] * (len(t2)+1) for _ in range(len(t1)+1)]
    for i in range(1, len(t1)+1):
        for j in range(1, len(t2)+1):
            if t1[i-1] == t2[j-1]: dp[i][j] = 1 + dp[i-1][j-1]
            else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[-1][-1]

Edit Distance — O(m·n)

def minDistance(w1, w2):
    m, n = len(w1), len(w2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1): dp[i][0] = i
    for j in range(n+1): dp[0][j] = j
    for i in range(1, m+1):
        for j in range(1, n+1):
            if w1[i-1] == w2[j-1]: dp[i][j] = dp[i-1][j-1]
            else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

← Heap Graphs →