Dynamic Programming

Dynamic Programming#

Transition from Divide and Conquer#

We have examined Divide and Conquer (D&C) algorithms, which solve problems by recursively breaking them into smaller, independent sub-problems. We now discuss a closely related paradigm: Dynamic Programming (DP).

Like D&C, Dynamic Programming simplifies a complex problem by breaking it down into simpler sub-problems, usually via recursion.

The critical difference lies in the nature of these sub-problems:

  • Divide and Conquer: Sub-problems are discrete and separate. For example, in Mergesort, an array element is never present in both the left and right sub-arrays.

  • Dynamic Programming: Sub-problems are overlapping. This means the same sub-problem is encountered multiple times during the computation.

Example 1: The Fibonacci Sequence#

The Fibonacci sequence is the sequence where each value in the sequence is the sum of the preceding two values. So, the sequence is 1, 1, 2, 3, 5, 8, 13... and so on (the next one is 21, because 8+13=21.

It is a common problem for students first learning recursion, because the nth Fibonacci number is equal to fib(n-1)+fib(n-2).

def fib(n):
    if n == 0 or n==1:
        return 1
    return fib(n-1)+fib(n-2)

Unfortunately, while correct, this solution is exponential, due to the fact that we compute values several times. If we trace the execution of fib(6), we find that fib(4) is computed twice, fib(3) is computed three times, and so on.

Dynamic programming avoids this waste by computing each sub-problem only once and storing the result. If we need that result again, we retrieve it from the table.

Approach 1: Memoization (Top-Down)#

Memoization is a DP technique that retains the top-down recursive structure but uses a lookup table (e.g., a dictionary) to store results as they are computed. This approach minimally changes the original program logic, and is now \(O(n)\), rather than \(O(2^n)\).

d = dict()
def fib_memo(n):
    if n==0 or n==1:
        return 1
    if n in d:
        return d[n]
    d[n] = fib_memo(n-1) + fib_memo(n-2)
    return d[n]

N = 39

import time
start = time.time()
ans = fib(N)
end = time.time()

print(f'Computed {ans} in {end-start} seconds')

start = time.time()
ans = fib_memo(N)
end = time.time()

print(f'Computed {ans} in {end-start} seconds')

Computed 102334155 in 5.159247875213623 seconds
Computed 102334155 in 3.719329833984375e-05 seconds

Approach 2: Tabulation (Bottom-Up)#

A more common DP approach is to build the solutions from the “bottom up.” We start by solving the smallest base cases and iteratively build up to the target value. This method avoids recursion limits and makes the table-building process explicit. This approach should clearly also be \(O(n)\).

def fib_tab(n):
    table = [1, 1] # table[0] = 1 and table[1] = 1
    for i in range(2, N+1):
        table.append( table[i-1] + table[i-2] )
    return table[N]

start = time.time()
ans = fib_tab(N)
end = time.time()

print(f'Computed {ans} in {end-start} seconds')

Computed 102334155 in 2.8133392333984375e-05 seconds

Memoization vs Tabulation#

Both memoization and tabulation are appropriate approaches. Memoization only calculates what is needed for some sub-problem, and has the added benefit to the programmer of not dramatically changing the coding flow of the original recursive function. However, it is recursive, and requires the overhead needed for recursion, such as a tall call stack.

Tabulation calculates the solution to all subproblems, whether or not it’s needed for the actual problem it’s called on. However, it is implemented iteratively, and so doesn’t require storage for the call stack.

“Which is best” is really determined by how many of the subproblems must be solved to calculate the problem solution. If you need them all (or nearly all) anyway, tabulation is most common. If you don’t, memoization is probably best.

Example 2: Change-Making Problem#

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

A greedy algorithm (always choosing the largest possible coin) is optimal for the standard US currency system. However, it is not optimal for all coin systems.

  • Counter-example: For a coin system with coins worth 1, 3, and 4, and a target amount of 6, the greedy algorithm fails.

    • Greedy: 4 + 1 + 1 (3 coins)

    • Optimal: 3 + 3 (2 coins)

Dynamic programming can solve this optimally through tabulation. We make a table count, where count[x] stores the minimum coins needed to make amount x. Starting from x=1, we increase x. Suppose we are trying to compute the solution for x=13, and we have coins worth 1, 6, and 9. The solution is the smallest of count[12]+1, count[7]+1, or count[4]+1.

In this implementation, coins is a list of coin values ([1, 6, 9]), and amount is the amount we are trying to compute for. It should be clear this is \(O(nk)\), where \(n\) is the number we’re computing for, and \(k\) is the number of coins.

def coin_change(coins, amount):
    # count array intialized with large values
    count = [float('inf')]*(amount+1)
    count[0] = 0 # Base case: count[0] = 0 because 0 coins needed to make amount 0

    # Fill array
    for x in range(1, amount + 1):
        for coin in coins:
            if x >= coin:
                # The minimum is either the current value
                # or the value from the subproblem (x - coin) + 1
                count[x] = min(count[x], count[x - coin] + 1)

    return count[amount]

coins = [1, 3, 4]
amount = 6
print(coin_change(coins, amount))

2

Example 3: 0-1 Knapsack Problem#

We previously identified the 0-1 Knapsack Problem as a case where the greedy strategy (based on value-to-weight ratio) fails to produce an optimal solution.

This problem does have an optimal solution via Dynamic Programming. The algorithm uses a 2D table, dp[i][w], to store the maximum value achievable using i total items with a maximum capacity of w.

This DP algorithm correctly solves the 0-1 Knapsack Problem, including the counter-example from the greedy algorithms lecture.

def knapsack(values, weights, capacity):
    n = len(values)
    # Create a DP table with (n+1) rows and (capacity+1) columns
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    # Fill the DP table
    for i in range(1, n + 1):  # Loop over items
        for w in range(capacity + 1):  # Loop over capacities
            
            # If the current item's weight is too much
            if weights[i - 1] > w:
                dp[i][w] = dp[i - 1][w]
            else:
                # Decide:
                # 1. Exclude the item: dp[i - 1][w]
                # 2. Include the item: dp[i - 1][w - weights[i - 1]] + values[i - 1]
                dp[i][w] = max(dp[i - 1][w], 
                               dp[i - 1][w - weights[i - 1]] + values[i - 1])

    # --- Code to find the selected items ---
    w = capacity
    selected_items = []
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:  # Item i-1 was included
            selected_items.append(i - 1)
            w -= weights[i - 1]

    return dp[n][capacity], selected_items[::-1]

This code constructs a solution iteratively by solving smaller sub-problems (fewer items, smaller capacities) and storing the results in a matrix (table) to avoid redundant calculations.

The code consists of two distinct phases: Tabulation and Backtracking.

Phase 1: Tabulation (Building the Matrix)

The goal of this phase is to determine the maximum value achievable for every possible capacity up to the limit.

  1. Initialization:

    • n = len(values): Determines the total number of items.

    • dp: A 2D matrix is initialized with zeros.

      • Rows (\(0\) to \(n\)): Represent the subset of items considered (e.g., row 2 considers only items 0 and 1).

      • Columns (\(0\) to \(capacity\)): Represent the current weight limit constraint \(w\) (from 0 up to the full capacity).

      • dp[i][w] stores the maximum value achievable using the first \(i\) items with a weight limit of \(w\).

  2. Iterative Logic (The Nested Loops): The code iterates through each item (item) and each potential weight capacity (w).

    • Case 1: Item is too heavy (weights[item - 1] > w) If the current item’s weight exceeds the current sub-capacity \(w\), it cannot be included. The maximum value remains the same as it was for the previous set of items (the value directly above in the table): $\(DP[i][w] = DP[i-1][w]\)$

    • Case 2: Item fits If the item fits, the algorithm must decide whether to include it or exclude it to maximize value. It calculates the max of two options:

      1. Exclude Item: Take the value from the previous row at the same capacity (\(DP[i-1][w]\)).

      2. Include Item: Add the current item’s value to the max value achieved with the remaining capacity (\(DP[i-1][w - weight_{current}] + value_{current}\)).

Phase 2: Backtracking (Finding the Items)

After filling the table, dp[n][capacity] contains the maximum total value. This phase identifies which items produced that value.

  1. Traversal: The code iterates backward from the last item (\(n\)) to the first.

  2. Detection Logic:

    • It checks if dp[item][w] != dp[item - 1][w].

    • If the value at the current row is different from the row above, it implies the current item was included to increase the value.

    • The item’s index is added to selected_items, and the current capacity w is reduced by that item’s weight to trace the remaining items.

    • If the value is the same, the item was excluded, and the loop proceeds to the previous item without changing w.

The function returns a tuple containing:

  1. The Maximum Value (\(DP[n][capacity]\)).

  2. The List of Selected Items (indices), reversed to show the order from first to last.