Dynamic Programming

Dynamic Programming

Dynamic Programming (DP) is a technique for solving problems by breaking them into smaller overlapping subproblems and storing the results to avoid recalculating them. This transforms slow recursive solutions into fast ones.

What You Need to Know

• The Problem: Some recursive solutions recalculate the same values many times, making them exponentially slow.
• The Solution: Store (cache) results the first time you calculate them, then reuse those stored results instead of recalculating.
• Two Approaches:
  • Memoization (top-down): Add caching to recursive solutions
  • Tabulation (bottom-up): Build up solutions iteratively using a table

When to Use DP

Use dynamic programming when:

• You can break the problem into smaller subproblems
• The same subproblems appear multiple times
• You can build the solution from smaller solutions

Example: Fibonacci Numbers

The Fibonacci sequence is a classic example. The naive recursive solution recalculates values exponentially, but DP makes it linear.

JavaKotlinTypeScriptDartSwiftPython

// Memoization (top-down with caching)
public int fibonacci(int n, int[] memo) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    return memo[n];
}

// Tabulation (bottom-up with table)
public int fibonacciTab(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// Memoization (top-down with caching)
fun fibonacci(n: Int, memo: IntArray = IntArray(n + 1)): Int {
    if (n <= 1) return n
    if (memo[n] != 0) return memo[n]
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]
}

// Tabulation (bottom-up with table)
fun fibonacciTab(n: Int): Int {
    if (n <= 1) return n
    val dp = IntArray(n + 1)
    dp[0] = 0
    dp[1] = 1
    for (i in 2..n) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

// Memoization (top-down with caching)
function fibonacci(n: number, memo: number[] = []): number {
    if (n <= 1) return n;
    if (memo[n]) return memo[n];
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    return memo[n];
}

// Tabulation (bottom-up with table)
function fibonacciTab(n: number): number {
    if (n <= 1) return n;
    const dp = new Array(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// Memoization (top-down with caching)
int fibonacci(int n, [List<int>? memo]) {
    memo ??= List.filled(n + 1, 0);
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    return memo[n];
}

// Tabulation (bottom-up with table)
int fibonacciTab(int n) {
    if (n <= 1) return n;
    List<int> dp = List.filled(n + 1, 0);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// Memoization (top-down with caching)
func fibonacci(_ n: Int, _ memo: inout [Int]) -> Int {
    if n <= 1 { return n }
    if memo[n] != 0 { return memo[n] }
    memo[n] = fibonacci(n - 1, &memo) + fibonacci(n - 2, &memo)
    return memo[n]
}

// Tabulation (bottom-up with table)
func fibonacciTab(_ n: Int) -> Int {
    if n <= 1 { return n }
    var dp = Array(repeating: 0, count: n + 1)
    dp[0] = 0
    dp[1] = 1
    for i in 2...n {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

# Memoization (top-down with caching)
def fibonacci(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

# Tabulation (bottom-up with table)
def fibonacci_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]

Dynamic programming is a powerful optimization technique that can dramatically speed up algorithms that have overlapping subproblems. The key is recognizing when to use it and choosing between memoization (easier to write from recursion) and tabulation (often more efficient).