Advanced Dynamic Programming: Classic Problem-Solving Techniques

In the previous article, we explored the fundamental concepts and applications of dynamic programming. Today, we’ll delve deeper into classic dynamic programming problems and their solutions. These problems not only reinforce our understanding of dynamic programming but also provide valuable insights for tackling more complex real-world challenges.

Classic Dynamic Programming Problems

1. Fibonacci Sequence

The Fibonacci sequence is the most basic example in dynamic programming. Computing the $n$-th Fibonacci number via naive recursion yields exponential time complexity—making it highly inefficient for large $n$. Dynamic programming offers an elegant optimization.

Solution:
Use an array dp to store intermediate results and avoid redundant computation:

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

Here, the time complexity is $O(n)$, and the space complexity is also $O(n)$. We can further optimize space usage to $O(1)$ by maintaining only the two most recent values:

def fibonacci_optimized(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

2. Longest Common Subsequence (LCS)

One of the most widely studied classic dynamic programming problems is the Longest Common Subsequence (LCS). Given two strings, the LCS problem asks for the longest subsequence common to both.

State Definition:

• Let dp[i][j] denote the length of the LCS between the first $i$ characters of string $A$ and the first $j$ characters of string $B$.

Transition Equation:

• If $A[i - 1] = B[j - 1]$, then $dp[i][j] = dp[i - 1][j - 1] + 1$.
• Otherwise, $dp[i][j] = \max(dp[i - 1][j],\ dp[i][j - 1])$.

Implementation:

def lcs(A, B):
    m, n = len(A), len(B)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[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]

3. 0–1 Knapsack Problem

The 0–1 knapsack problem is a canonical optimization problem: given a set of items—each with a weight and a value—select a subset to maximize total value without exceeding a given weight capacity. Each item may be chosen at most once.

State Definition:

• Let dp[i][j] represent the maximum value achievable using the first $i$ items and a knapsack capacity of $j$.

Transition Equation:

• If $j < w[i]$: $dp[i][j] = dp[i - 1][j]$
• If $j \geq w[i]$: $dp[i][j] = \max\big(dp[i - 1][j],\ dp[i - 1][j - w[i]] + v[i]\big)$

Implementation:

def knapsack(weights, values, capacity):
    n = len(values)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(capacity + 1):
            if j < weights[i - 1]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])

    return dp[n][capacity]

4. Coin Change (Number of Combinations)

Given coins of various denominations and a target amount, compute the number of distinct ways to make up that amount using the available coins.

State Definition:

• Let dp[j] denote the number of combinations to form amount $j$.

Transition Equation:

• For each coin coin, update: $dp[j] \mathrel{+}= dp[j - \text{coin}]$

Implementation:

def coin_change(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1  # Base case: one way to make amount 0 (use no coins)

    for coin in coins:
        for j in range(coin, amount + 1):
            dp[j] += dp[j - coin]

    return dp[amount]

Summary

Through the analysis and implementation of these classic dynamic programming problems, we see that dynamic programming is not merely a technical tool—it’s a structured way of thinking. When approaching such problems, clearly defining the state, deriving the recurrence relation, and establishing proper base cases are essential steps.

In the next article, we’ll explore state-compressed dynamic programming, a powerful technique that reduces space complexity by representing states more compactly—often using bitmasks or rolling arrays. Stay tuned!