Dynamic Programming

Overview

Dynamic Programming (DP) is an optimization technique used to solve problems by breaking them into overlapping subproblems and storing their results to avoid redundant work. It’s particularly effective for problems with optimal substructure and overlapping subproblems.

Key Concepts

Optimal Substructure: The optimal solution to the problem can be built from optimal solutions to its subproblems.
Overlapping Subproblems: The problem can be broken down into subproblems which are reused multiple times.
Memoization: Top-down approach that caches results of recursive calls.
Tabulation: Bottom-up approach that builds a solution iteratively using a table.

Fibonacci with Memoization (Top-Down)

func fibMemo(_ n: Int, _ memo: inout [Int: Int]) -> Int {
    if n <= 1 { return n }
    if let result = memo[n] { return result }
    memo[n] = fibMemo(n - 1, &memo) + fibMemo(n - 2, &memo)
    return memo[n]!
}

// Usage
var memo: [Int: Int] = [:]
let result = fibMemo(10, &memo)
print(result) // 55

Fibonacci with Tabulation (Bottom-Up)

func fibTab(_ n: Int) -> Int {
    if n <= 1 { return n }
    var dp = [0, 1]
    for i in 2...n {
        dp.append(dp[i - 1] + dp[i - 2])
    }
    return dp[n]
}

0/1 Knapsack Problem

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value.

func knapsack(_ weights: [Int], _ values: [Int], _ capacity: Int) -> Int {
    let n = weights.count
    var dp = Array(repeating: Array(repeating: 0, count: capacity + 1), count: n + 1)

    for i in 1...n {
        for w in 0...capacity {
            if weights[i - 1] <= w {
                dp[i][w] = max(dp[i - 1][w],
                               dp[i - 1][w - weights[i - 1]] + values[i - 1])
            } else {
                dp[i][w] = dp[i - 1][w]
            }
        }
    }

    return dp[n][capacity]
}

Longest Common Subsequence (LCS)

func lcs(_ text1: String, _ text2: String) -> Int {
    let t1 = Array(text1)
    let t2 = Array(text2)
    let m = t1.count, n = t2.count
    var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: m + 1)

    for i in 1...m {
        for j in 1...n {
            if t1[i - 1] == t2[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]
}

Coin Change Problem

Find the fewest number of coins needed to make up a given amount.

func coinChange(_ coins: [Int], _ amount: Int) -> Int {
    var dp = Array(repeating: amount + 1, count: amount + 1)
    dp[0] = 0

    for i in 1...amount {
        for coin in coins where coin <= i {
            dp[i] = min(dp[i], dp[i - coin] + 1)
        }
    }

    return dp[amount] > amount ? -1 : dp[amount]
}

Tips for Dynamic Programming

Identify overlapping subproblems.
Choose between memoization (recursive) and tabulation (iterative).
Define state and recurrence relation clearly.
Use 1D or 2D arrays depending on the problem.

Summary

Dynamic Programming is a powerful tool that turns exponential-time problems into polynomial-time solutions. Mastery of DP unlocks the ability to tackle a wide variety of optimization and counting problems with confidence and precision.