DSA Dynamic Programming

Dynamic Programming (DP) is an advanced algorithmic technique used to solve problems that can be broken down into overlapping subproblems. Instead of solving the same subproblem repeatedly, DP stores the results of already-solved subproblems and reuses them — dramatically reducing computation time.

The term "dynamic" is a historical name and does not directly mean "changing." DP is fundamentally about smart caching of intermediate results to avoid redundant work.

When to Use Dynamic Programming

A problem is a good candidate for DP if it has two key properties:

1. Overlapping Subproblems

The same subproblems are solved multiple times. For example, computing Fibonacci(5) requires Fibonacci(4) and Fibonacci(3), but Fibonacci(3) is also needed when computing Fibonacci(4).

2. Optimal Substructure

The optimal solution to the entire problem can be built from optimal solutions of its subproblems. For example, the shortest path from A to C through B is the shortest path from A to B plus the shortest path from B to C.

Two Approaches to Dynamic Programming

1. Top-Down: Memoization

Use recursion but store results in a cache (usually a dictionary or array). When a subproblem is encountered, check the cache first. If already solved, return the stored result instead of recomputing.

2. Bottom-Up: Tabulation

Solve subproblems iteratively in order, building up from the smallest case. Store results in a table (array) and use previously computed values to solve larger problems.

Classic Example: Fibonacci Sequence

Naive Recursion — O(2ⁿ)

def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)
# Very slow for large n — computes same values many times

Top-Down DP with Memoization — O(n)

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]     # Already computed — return cached result
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

print(fib_memo(40))   # Output: 102334155 (instant!)

Bottom-Up DP with Tabulation — O(n)

def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(fib_tab(50))   # Output: 12586269025

The Coin Change Problem

Given a set of coin denominations and a target amount, find the minimum number of coins needed to make up that amount.

def coin_change(coins, amount):
    # dp[i] = minimum coins needed to make amount i
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0   # Zero coins needed for amount 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

print(coin_change([1, 5, 6, 9], 11))   # Output: 2  (5 + 6)
print(coin_change([2], 3))             # Output: -1 (impossible)

The 0/1 Knapsack Problem

Given items with weights and values, and a bag with a maximum weight capacity, find the maximum value that can be carried. Each item can be taken once (0 or 1 time).

def knapsack(weights, values, capacity):
    n = len(weights)
    # dp[i][w] = max value using first i items with capacity w
    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 it fits)
            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]

weights = [1, 3, 4, 5]
values  = [1, 4, 5, 7]
capacity = 7

print(knapsack(weights, values, capacity))   # Output: 9

Longest Common Subsequence (LCS)

Given two strings, find the length of their longest common subsequence — a sequence that appears in both strings in the same relative order (not necessarily contiguous).

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]

print(lcs("ABCBDAB", "BDCABA"))   # Output: 4 (e.g., BCBA or BDAB)

Longest Increasing Subsequence (LIS)

def lis(arr):
    n = len(arr)
    dp = [1] * n   # Each element is a subsequence of length 1 on its own

    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

print(lis([10, 9, 2, 5, 3, 7, 101, 18]))   # Output: 4 (e.g., 2, 3, 7, 18)

Python's functools.lru_cache for Memoization

Python provides a built-in decorator that automatically memoizes function results, making it easy to add caching to recursive functions.

from functools import lru_cache

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

print(fib(100))   # Output: 354224848179261915075 (instant!)

Big O Summary for DP Problems

• Fibonacci (DP) — O(n) time, O(n) space; optimized to O(1) space
• Coin Change — O(amount × coins) time, O(amount) space
• 0/1 Knapsack — O(n × capacity) time, O(n × capacity) space
• LCS — O(m × n) time and space
• LIS — O(n²) time; O(n log n) with binary search optimization

Key Points

• Dynamic programming solves problems with overlapping subproblems and optimal substructure.
• Memoization (top-down) adds caching to recursion; tabulation (bottom-up) fills a table iteratively.
• DP can reduce exponential time complexity to polynomial (e.g., Fibonacci: O(2ⁿ) → O(n)).
• Classic DP problems include Fibonacci, Coin Change, Knapsack, LCS, and LIS.
• Python's @lru_cache decorator is the easiest way to add memoization to any recursive function.
• Mastering DP requires recognizing the pattern and defining the right state for the dp table.