An Intro to Algorithms: Dynamic Programming

Dynamic programming is a powerful algorithmic technique that can solve a wide variety of optimization and counting problems efficiently. It is an essential tool in any professional programmer or computer scientist‘s toolkit. In this article, we‘ll dive into what dynamic programming is, understand the characteristics of problems it can solve, look at classic examples, and analyze its strengths and limitations.

What is dynamic programming?

Dynamic programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems, solving each subproblem once, and storing their solutions to avoid redundant computation. The key idea is to solve each subproblem optimally and combine their optimal solutions to obtain the overall optimal solution to the original problem.

DP applies to problems with two key attributes:

1. Overlapping subproblems – the problem can be broken down into subproblems which are reused multiple times

2. Optimal substructure – an optimal solution can be constructed from optimal solutions of its subproblems

Many real-world optimization problems exhibit these properties, such as finding the shortest path in a graph, maximizing revenue, minimizing cost, or counting the number of ways to do something. DP provides efficient algorithms to tackle these challenging problems.

Characteristics of dynamic programming problems

Not all optimization problems can be solved using DP. A problem must have certain characteristics to be a good candidate for dynamic programming:

1. The problem can be divided into subproblems that overlap. Solving the original problem requires solving the same subproblems repeatedly.

2. The solution to the original problem is a combination of optimal solutions to subproblems. This is known as the optimal substructure property.

3. The problem has a recursive formulation. The solution can be defined recursively in terms of solutions to smaller subproblems.

4. The number of distinct subproblems is typically polynomial in the input size. This allows storing and looking up solutions efficiently.

If a problem meets these criteria, then it might be solvable using dynamic programming techniques. Two main approaches exist: memoization and tabulation.

Approaches to solving DP problems

Memoization (top-down)

Memoization is a top-down approach that starts with the original problem and recursively breaks it down into subproblems. As subproblems are solved, their results are cached in a lookup table to avoid recomputing them.

Here‘s a template for applying memoization to a problem:

def memoize(func):
    cache = {}
    def wrapper(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrapper

@memoize
def recursive_solve(problem):
    if base_case(problem):
        return base_result

    subproblems = split_problem(problem)
    subresults = [recursive_solve(subproblem) for subproblem in subproblems]
    result = combine_results(subresults)
    return result

This pseudo-Python code defines a memoize decorator that wraps a recursive function, intercepting its arguments and caching the computed result. The recursive function recursive_solve breaks down the problem into subproblems, recursively solves each one, and combines their results. Memoization avoids repeated subproblem solving.

Tabulation (bottom-up)

Tabulation works bottom-up by starting with trivially solvable base cases and incrementally building up solutions to larger subproblems until the original problem is solved. The results are stored in a table to be looked up and combined.

A tabulation template looks like:

def iterative_solve(problem):
    table = initialize_table(problem)

    for i in range(base_case, problem_size):
        subproblems = generate_subproblems(i)
        subresults = [table[subproblem] for subproblem in subproblems]
        table[i] = combine_results(subresults)

    return table[problem_size - 1]

This iterative function initializes a lookup table, then fills it in a bottom-up manner. For each problem size, it generates relevant subproblems, looks up their precomputed solutions, and combines them into a solution to the current subproblem, storing it in the table.

Both memoization and tabulation typically have a time and space complexity based on the number of distinct subproblems. Trading increased memory usage for exponential speedup is often a worthwhile tradeoff.

Classic examples

Let‘s look at some well-known problems that can be effectively solved using dynamic programming.

Fibonacci sequence

The Fibonacci sequence is defined recursively as:

fib(0) = 0
fib(1) = 1 
fib(n) = fib(n-1) + fib(n-2) for n > 1

A naive recursive implementation has exponential time complexity due to redundant subcalls. Applying memoization gives linear time and space complexity:

@memoize
def fib(n):
    if n < 2:
        return n
    else:
        return fib(n-1) + fib(n-2)

The tabulation version builds the sequence bottom-up:

def fib(n):
    fib_table = [0] * (n+1)
    fib_table[1] = 1
    for i in range(2, n+1):
        fib_table[i] = fib_table[i-1] + fib_table[i-2]
    return fib_table[n]

0/1 Knapsack problem

Given a set of items, each with a weight and value, determine the maximum total value that can fit in a knapsack of fixed capacity. Each item is indivisible and can be included at most once.

This can be solved with the recurrence:

knapsack(n, C) = max(knapsack(n-1, C), knapsack(n-1, C-w[n]) + v[n]) if w[n] ≤ C
                 knapsack(n-1, C)                                    if w[n] > C

Where knapsack(n, C) is the maximum value that can be obtained using items 1 through n and total capacity C. We consider including the nth item if it fits, or excluding it.

The memoized solution is:

@memoize
def knapsack(n, C):
    if n == 0 or C == 0:
        return 0
    elif weights[n] > C:
        return knapsack(n-1, C)
    else:
        return max(knapsack(n-1, C), knapsack(n-1, C-weights[n]) + values[n])

And the tabulation approach:

def knapsack(weights, values, C):
    n = len(weights)
    table = [[0] * (C+1) for _ in range(n+1)]

    for i in range(1, n+1):
        for j in range(1, C+1):
            if weights[i-1] <= j:
                table[i][j] = max(values[i-1] + table[i-1][j-weights[i-1]], table[i-1][j]) 
            else:
                table[i][j] = table[i-1][j]

    return table[n][C]

Both versions have O(nC) time and space complexity, where n is the number of items and C the knapsack capacity. This is pseudopolynomial since it depends on the capacity value C.

Longest common subsequence

The longest common subsequence (LCS) problem aims to find the longest subsequence common to two sequences. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order.

The LCS has an optimal substructure property. Let X[1..m] and Y[1..n] be two sequences and Z[1..l] be their LCS. Then:

• If X[m] = Y[n], then Z[l] = X[m] = Y[n] and Z[1..l-1] is an LCS of X[1..m-1] and Y[1..n-1].
• If X[m] ≠ Y[n], then Z[l] ≠ X[m] implies Z is an LCS of X[1..m-1] and Y[1..n].
• If X[m] ≠ Y[n], then Z[l] ≠ Y[n] implies Z is an LCS of X[1..m] and Y[1..n-1].

This leads to the recurrence:

lcs(m, n) = lcs(m-1, n-1) + 1                 if X[m] = Y[n]
            max(lcs(m, n-1), lcs(m-1, n))     if X[m] ≠ Y[n]

With base cases lcs(0, *) and lcs(*, 0) being 0.

Here‘s the tabulation version:

def lcs(X, Y):
    m, n = len(X), len(Y)
    table = [[0] * (n+1) for _ in range(m+1)]

    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                table[i][j] = table[i-1][j-1] + 1
            else:
                table[i][j] = max(table[i][j-1], table[i-1][j])

    return table[m][n]

The time and space complexity is O(mn), making it an efficient solution.

Analysis of DP algorithms

Dynamic programming provides polynomial time algorithms for many problems that have exponential naive solutions. DP algorithms typically have a running time of O(nd) for some constants d, where n is the size of the input. The exponent d is usually the number of variables used to describe a subproblem.

The space complexity is also typically polynomial, often the same as the time complexity since DP tables store solutions to all subproblems. However, for some problems, space can be optimized by only storing the last few levels of subproblems necessary for the computation.

When to use dynamic programming

Dynamic programming is applicable in many domains such as optimization, scheduling, sequence analysis, graph algorithms, and counting problems. Signs that a problem might be solvable by DP include:

• The problem exhibits overlapping subproblems and optimal substructure
• The problem has a recursive formulation
• Brute force solutions involve exponential enumeration of possibilities
• The problem seeks an optimal solution among multiple options

If a greedy algorithm does not obviously solve a problem optimally, it is often worthwhile to consider a DP approach. However, not all optimization problems are amenable to dynamic programming.

Limitations and challenges

Dynamic programming is a powerful technique, but it also has some drawbacks and challenges:

1. DP algorithms can be tricky to formulate. Identifying the right subproblems and recurrence relation requires careful analysis and insight. Minor variations in a problem statement can lead to very different DP formulations.

2. DP solutions can have high memory overhead as they store solutions to all subproblems. For problems with multidimensional state spaces, memory usage can become prohibitive. Techniques like space optimization and divide-and-conquer can help mitigate this issue.

3. Some problems may not have the optimal substructure property required for DP to work. Greedy or other approaches may be more suitable in such cases.

4. The constants hidden in the asymptotic complexity of DP algorithms can be quite large, making them impractical for some instances. Approaches like pruning unnecessary subproblem computations can help speed up the algorithms.

Despite these challenges, DP remains an indispensable tool for algorithm design and optimization. Recognizing when it is applicable and skillfully wielding it is an essential ability.

History and origin

The term "dynamic programming" was coined by mathematician Richard Bellman in the 1950s while working at RAND Corporation. Bellman used the adjective "dynamic" to capture the notion of a problem being solved by a multi-stage decision process and "programming" as a synonym for optimization, making it a catchy yet opaque name unrelated to computer programming.

Ironically, the secretary of defense at the time had a bias against mathematical research, so Bellman deliberately chose the vague name "dynamic programming" to shield his work from scrutiny, writing in his autobiography: "I used the word ‘programming‘ to hide what I was really doing."

The field of dynamic programming has since flourished and found applications in control theory, operations research, computer science, and many other domains dealing with optimizing multi-stage decision processes.

Conclusion

Dynamic programming is a powerful problem-solving technique that combines recursion and memoization to efficiently compute optimal solutions to problems with overlapping subproblems and optimal substructure. By solving subproblems once and caching their solutions, DP algorithms avoid exponential brute force enumeration and redundant computation.

While formulating DP solutions and managing space usage can be challenging, the technique is widely applicable for optimization in various domains. Classic problems like Knapsack, Fibonacci, and longest common subsequence showcase its effectiveness.

Understanding dynamic programming is essential for any practicing programmer or computer science student. With this gentle introduction, you should be ready to recognize when DP might apply, formulate recursive top-down or iterative bottom-up solutions, and analyze time and space complexity. Happy problem solving!