Dynamic Programming

📖 Introduction

Dynamic programming (DP) was the concept that took me the longest to truly understand. I remember staring at the Fibonacci memoization solution thinking "okay, I see why this works" but not really understanding when to apply it elsewhere.

The breakthrough came when I realized DP is just smart recursion—breaking problems into overlapping subproblems and reusing solutions. Once I started recognizing the patterns, problems that seemed impossible became systematic.

---

🎯 What Is Dynamic Programming?

DP solves problems by:

1. Breaking them into overlapping subproblems

2. Storing results to avoid recomputation

3. Building solutions from smaller optimal substructures

When to Use DP

Signs a problem is DP:

• Asks for optimal (min/max), count of ways, or possibility (can/cannot)

• Future decisions depend on earlier decisions

• Same subproblem computed multiple times

---

🔝 Top-Down (Memoization)

Start with the original problem, recurse down, cache results.

from functools import lru_cache

# Classic Fibonacci
def fib_naive(n: int) -> int:
    """O(2^n) - exponential, many repeated calls."""
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)


def fib_memo(n: int, memo: dict = None) -> int:
    """O(n) with memoization."""
    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]


@lru_cache(maxsize=None)
def fib_lru(n: int) -> int:
    """O(n) using Python's built-in cache."""
    if n <= 1:
        return n
    return fib_lru(n - 1) + fib_lru(n - 2)

Visualizing Memoization

Memoization eliminates duplicate calls—fib(3) computed once instead of twice.

---

⬆️ Bottom-Up (Tabulation)

Start with base cases, build up to the solution iteratively.

def fib_tabulation(n: int) -> int:
    """O(n) time, O(n) space."""
    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]


def fib_optimized(n: int) -> int:
    """O(n) time, O(1) space."""
    if n <= 1:
        return n
    
    prev2, prev1 = 0, 1
    
    for _ in range(2, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    
    return prev1

Top-Down vs Bottom-Up

Aspect	Top-Down	Bottom-Up
Implementation	Recursive + cache	Iterative + table
Order	Natural problem order	Must determine order
Subproblems	Only needed ones	All subproblems
Stack	Uses call stack	No stack overflow
Readability	Often more intuitive	Can be harder to derive

---

📊 DP Framework

Step-by-Step Approach

1. Define State: What variables describe a subproblem?

2. Define Transition: How to compute state from smaller states?

3. Define Base Cases: What are the smallest subproblems?

4. Define Answer: How to get final answer from states?

5. Optimize Space: Can we reduce memory usage?

---

🎯 Classic DP Patterns

Pattern 1: Linear DP

Climbing Stairs

def climb_stairs(n: int) -> int:
    """
    Ways to climb n stairs (1 or 2 steps at a time).
    State: dp[i] = ways to reach step i
    Transition: dp[i] = dp[i-1] + dp[i-2]
    """
    if n <= 2:
        return n
    
    prev2, prev1 = 1, 2
    
    for _ in range(3, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    
    return prev1

House Robber

def rob(nums: list[int]) -> int:
    """
    Max money without robbing adjacent houses.
    State: dp[i] = max money from first i houses
    Transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    """
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    prev2, prev1 = 0, nums[0]
    
    for i in range(1, len(nums)):
        current = max(prev1, prev2 + nums[i])
        prev2, prev1 = prev1, current
    
    return prev1


# House Robber II (circular)
def rob_circular(nums: list[int]) -> int:
    """Houses form a circle - can't rob first AND last."""
    if len(nums) == 1:
        return nums[0]
    
    def rob_range(start, end):
        prev2, prev1 = 0, 0
        for i in range(start, end):
            current = max(prev1, prev2 + nums[i])
            prev2, prev1 = prev1, current
        return prev1
    
    # Either skip first or skip last
    return max(rob_range(0, len(nums) - 1), rob_range(1, len(nums)))

Maximum Subarray (Kadane's Algorithm)

def max_subarray(nums: list[int]) -> int:
    """
    Find contiguous subarray with largest sum.
    State: dp[i] = max sum ending at index i
    Transition: dp[i] = max(nums[i], dp[i-1] + nums[i])
    """
    max_sum = current_sum = nums[0]
    
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    
    return max_sum

Pattern 2: 2D Grid DP

Unique Paths

def unique_paths(m: int, n: int) -> int:
    """
    Ways to go from top-left to bottom-right (only down/right).
    State: dp[i][j] = paths to reach (i, j)
    """
    dp = [[1] * n for _ in range(m)]
    
    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]


# Space optimized
def unique_paths_optimized(m: int, n: int) -> int:
    dp = [1] * n
    
    for _ in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j-1]
    
    return dp[n-1]

Minimum Path Sum

def min_path_sum(grid: list[list[int]]) -> int:
    """
    Minimum sum path from top-left to bottom-right.
    """
    m, n = len(grid), len(grid[0])
    
    # Fill first row
    for j in range(1, n):
        grid[0][j] += grid[0][j-1]
    
    # Fill first column
    for i in range(1, m):
        grid[i][0] += grid[i-1][0]
    
    # Fill rest
    for i in range(1, m):
        for j in range(1, n):
            grid[i][j] += min(grid[i-1][j], grid[i][j-1])
    
    return grid[m-1][n-1]

Pattern 3: Subsequence DP

Longest Increasing Subsequence (LIS)

def length_of_lis(nums: list[int]) -> int:
    """
    Length of longest strictly increasing subsequence.
    State: dp[i] = LIS ending at index i
    O(n²) solution
    """
    if not nums:
        return 0
    
    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) solution using binary search
def length_of_lis_optimized(nums: list[int]) -> int:
    from bisect import bisect_left
    
    sub = []  # Smallest ending element for each length
    
    for num in nums:
        pos = bisect_left(sub, num)
        if pos == len(sub):
            sub.append(num)
        else:
            sub[pos] = num
    
    return len(sub)

Longest Common Subsequence (LCS)

def longest_common_subsequence(text1: str, text2: str) -> int:
    """
    Length of longest common subsequence.
    State: dp[i][j] = LCS of text1[:i] and text2[:j]
    """
    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]


# Reconstruct the subsequence
def get_lcs(text1: str, text2: str) -> str:
    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])
    
    # Backtrack
    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if text1[i-1] == text2[j-1]:
            result.append(text1[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    
    return ''.join(reversed(result))

Pattern 4: Knapsack Problems

0/1 Knapsack

def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    """
    Max value with limited capacity (each item used once).
    State: dp[i][w] = max value using first i items with capacity w
    """
    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):
            # Don't take item i
            dp[i][w] = dp[i-1][w]
            
            # Take item i if possible
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1])
    
    return dp[n][capacity]


# Space optimized (single row)
def knapsack_optimized(weights: list[int], values: list[int], capacity: int) -> int:
    dp = [0] * (capacity + 1)
    
    for i in range(len(weights)):
        # Iterate backwards to avoid using updated values
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]

Unbounded Knapsack (Coin Change)

def coin_change(coins: list[int], amount: int) -> int:
    """
    Min coins needed to make amount (unlimited coins).
    Return -1 if impossible.
    """
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1


def coin_change_ways(coins: list[int], amount: int) -> int:
    """
    Number of ways to make amount.
    """
    dp = [0] * (amount + 1)
    dp[0] = 1
    
    # Iterate coins first to count combinations (not permutations)
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]
    
    return dp[amount]

Pattern 5: String DP

Edit Distance

def min_distance(word1: str, word2: str) -> int:
    """
    Min operations (insert, delete, replace) to convert word1 to word2.
    State: dp[i][j] = min ops for word1[:i] to word2[:j]
    """
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Base cases
    for i in range(m + 1):
        dp[i][0] = i  # Delete all
    for j in range(n + 1):
        dp[0][j] = j  # Insert all
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j],     # Delete
                    dp[i][j-1],     # Insert
                    dp[i-1][j-1]    # Replace
                )
    
    return dp[m][n]

Palindrome Substrings

def count_palindromic_substrings(s: str) -> int:
    """
    Count all palindromic substrings.
    """
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    count = 0
    
    # All single chars are palindromes
    for i in range(n):
        dp[i][i] = True
        count += 1
    
    # Check pairs
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            count += 1
    
    # Check longer substrings
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                count += 1
    
    return count


# Expand around center approach (O(1) space)
def count_palindromes_expand(s: str) -> int:
    def expand(left, right):
        count = 0
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
        return count
    
    total = 0
    for i in range(len(s)):
        total += expand(i, i)      # Odd length
        total += expand(i, i + 1)  # Even length
    
    return total

Pattern 6: Interval DP

Burst Balloons

def max_coins(nums: list[int]) -> int:
    """
    Max coins from bursting balloons.
    nums[i-1] * nums[i] * nums[i+1] coins when bursting i.
    """
    # Add boundaries
    nums = [1] + nums + [1]
    n = len(nums)
    
    dp = [[0] * n for _ in range(n)]
    
    # dp[i][j] = max coins for bursting all between i and j
    for length in range(2, n):
        for left in range(n - length):
            right = left + length
            
            # k is the last balloon to burst in range
            for k in range(left + 1, right):
                dp[left][right] = max(
                    dp[left][right],
                    dp[left][k] + dp[k][right] + 
                    nums[left] * nums[k] * nums[right]
                )
    
    return dp[0][n - 1]

---

🧠 DP Problem Recognition

Key Phrases

Phrase	Likely DP Type
"Minimum/maximum"	Optimization DP
"Count ways"	Counting DP
"Is it possible"	Boolean DP
"Longest/shortest"	Sequence DP
"Partition into"	Knapsack variant

---

📝 Practice Exercises

Exercise 1: Decode Ways

def num_decodings(s: str) -> int:
    """
    Ways to decode string of digits.
    'A' = 1, 'B' = 2, ..., 'Z' = 26
    
    "12" -> 2 ("AB" or "L")
    "226" -> 3 ("BZ", "VF", or "BBF")
    """
    pass

Solution

def num_decodings(s: str) -> int:
    if not s or s[0] == '0':
        return 0
    
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    
    for i in range(2, n + 1):
        # Single digit
        if s[i-1] != '0':
            dp[i] += dp[i-1]
        
        # Two digits
        two_digit = int(s[i-2:i])
        if 10 <= two_digit <= 26:
            dp[i] += dp[i-2]
    
    return dp[n]

Exercise 2: Word Break

def word_break(s: str, word_dict: list[str]) -> bool:
    """
    Can s be segmented into words from word_dict?
    
    s = "leetcode", wordDict = ["leet", "code"] -> True
    s = "applepenapple", wordDict = ["apple", "pen"] -> True
    """
    pass

Solution

def word_break(s: str, word_dict: list[str]) -> bool:
    word_set = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    
    return dp[n]

Exercise 3: Longest Palindromic Substring

def longest_palindrome(s: str) -> str:
    """
    Find longest palindromic substring.
    
    "babad" -> "bab" or "aba"
    "cbbd" -> "bb"
    """
    pass

Solution

def longest_palindrome(s: str) -> str:
    n = len(s)
    if n < 2:
        return s
    
    start, max_len = 0, 1
    
    def expand(left, right):
        nonlocal start, max_len
        while left >= 0 and right < n and s[left] == s[right]:
            if right - left + 1 > max_len:
                start = left
                max_len = right - left + 1
            left -= 1
            right += 1
    
    for i in range(n):
        expand(i, i)      # Odd
        expand(i, i + 1)  # Even
    
    return s[start:start + max_len]

---

🔑 Key Takeaways

1. Identify overlapping subproblems and optimal substructure

2. Top-down is often more intuitive; bottom-up avoids stack overflow

3. State definition is crucial—ask "what do I need to know?"

4. Space optimization is usually possible by keeping only needed states

5. Practice patterns: linear, grid, subsequence, knapsack, string, interval

---

🚀 What's Next?

In the next article, we'll explore greedy algorithms and backtracking:

• Greedy choice property

• Interval scheduling

• Backtracking template

• Pruning strategies

Next: Article 13 - Greedy & Backtracking

---

📚 References

• CLRS Chapter 15: Dynamic Programming

• "Introduction to Algorithms" - DP examples

• LeetCode DP study plan