Demystifying Dynamic Programming

Dynamic programming (DP) is one of the most powerful and commonly used techniques for solving optimization problems. However, DP is also one of the most challenging topics for people learning algorithms and preparing for coding interviews. Many struggle with identifying the sub-problems and defining the recurrence relation. It can seem like magic when you see a DP solution if you don‘t understand the underlying principles.

The goal of this post is to demystify dynamic programming and provide a step-by-step guide to solving DP problems. We‘ll go through several classic examples and analyze the time and space complexity. By the end, you‘ll have a solid foundation for applying DP to optimize solutions to challenging problems.

What is Dynamic Programming?

At a high level, dynamic programming is an optimization technique that solves complex problems by breaking them down into simpler sub-problems. The key idea is to avoid redundant calculations by reusing previously computed results. We store the solutions to the sub-problems and use them to build up to the overall solution, which saves time compared to a naive approach that solves the same sub-problems repeatedly.

The term "dynamic programming" is a bit of a misnomer. It isn‘t related to writing programs dynamically or any specific programming language. The "programming" refers to using a table or array. The technique was invented by mathematician Richard Bellman in the 1950s, who used the term because it sounded impressive at the time, before computer programming was widespread.

When to Use Dynamic Programming

A problem must have certain characteristics to be a good candidate for dynamic programming:

1. Optimal substructure – an optimal solution can be constructed from optimal solutions of its sub-problems.
2. Overlapping sub-problems – sub-problems are reused several times to solve the original problem.

Optimal substructure means a problem can be broken down into smaller sub-problems, which can be solved independently. We can find the optimal solution to the original problem by combining optimal solutions to the sub-problems. Overlapping sub-problems means the recursive algorithm would visit the same sub-problems repeatedly. A DP solution solves each sub-problem only once and stores the result for future use.

Many problems that can be solved by recursion with exponential time can be optimized with dynamic programming to have polynomial time instead. Whenever you write a recursive solution and notice that you‘re solving the same sub-problems repeatedly, consider caching the results to optimize it – this is the essence of dynamic programming.

General Steps to Solve a DP Problem

Here are the key steps to solve a problem using dynamic programming:

1. Identify the sub-problems
2. Define the recurrence relation between sub-problems
3. Determine the base cases
4. Decide if you want to implement it iteratively or recursively with memoization
5. Add the results of the sub-problems to arrive at the final solution

Let‘s go through some examples to make these steps concrete.

Example 1: Fibonacci Numbers

The Fibonacci sequence is a classic example to illustrate dynamic programming. The sequence starts with 0 and 1. Each subsequent number is the sum of the previous two numbers:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

If we defined it as a mathematical recurrence relation:

• Base cases: fib(0) = 0, fib(1) = 1
• Recurrence relation: fib(n) = fib(n-1) + fib(n-2) for n > 1

A naive recursive solution would look like:

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

However, this has exponential O(2^n) time complexity because it computes the same Fibonacci numbers over and over. We can optimize it using dynamic programming by caching the results:

def fib(n):
memo = {}
def fib_memo(n):
if n < 2:
return n
if n in memo:
return memo[n] else:
memo[n] = fib_memo(n-1) + fib_memo(n-2)
return memo[n] return fib_memo(n)

This brings the time complexity down to O(n). The space complexity is O(n) as well to store the memo table.

We can also implement it iteratively and optimize the space to O(1) by only storing the last two numbers:

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

Both the recursive memoized and iterative solutions avoid redundant calculations and have linear time complexity. The iterative one is more space efficient as it only uses O(1) extra space.

Example 2: Knapsack Problem

The Knapsack problem is a classic example of dynamic programming. Given a set of items, each with a weight and a value, determine the items to include in a knapsack to maximize the total value without exceeding the weight limit.

For example, say we have the following items:

Item	Weight	Value
1	2	$6
2	2	$10
3	3	$12

The maximum weight our knapsack can hold is 5. Which items should we take to maximize value?

Let‘s define it formally:

• Input: Weights w1, w2, …, wn; Values v1, v2, …, vn; Knapsack capacity W
• Objective: Maximize sum of values of items in knapsack so that sum of weights is less than or equal to W

We can break it down into sub-problems:

• Let DP[i][w] be the maximum value of items 1, 2, …, i with weight limit w
• For each item i, we have two options:
  1. Don‘t include item i: DP[i][w] = DP[i-1][w]
  2. Include item i: DP[i][w] = vi + DP[i-1][w-wi] if wi <= w
• Our final answer will be DP[n][W], the maximum value possible with all n items and full capacity W

Here is the recurrence relation:

• DP[0][w] = 0 for all w (base case)
• DP[i][0] = 0 for all i (base case)
• DP[i][w] = max(DP[i-1][w], vi + DP[i-1][w-wi]) if wi <= w, otherwise just DP[i-1][w]

We can implement it as a 2D array DP[i][w]. The first dimension i represents the first i items. The second dimension w represents a weight limit from 0 to W.

Here‘s the code for a bottom-up iterative solution:

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

for i in range(1, n+1):
    for w in range(1, capacity+1):
        if weights[i-1] <= w:
            DP[i][w] = max(values[i-1] + DP[i-1][w-weights[i-1]], DP[i-1][w]) 
        else:
            DP[i][w] = DP[i-1][w]

return DP[n][capacity]

The time and space complexity are both O(nW), where n is the number of items and W is the capacity. We can optimize the space further to O(W) by only storing the last two rows of the DP table since that‘s all we need to compute a new row.

Example 3: Longest Common Subsequence

Another classic dynamic programming problem is finding the longest common subsequence (LCS) between two strings. This has applications in bioinformatics for comparing gene sequences.

A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, "abc" is a subsequence of "abcdef" but "acb" is not.

Given two strings, find the length of their longest common subsequence. For example:

• LCS for input Sequences "ABCDGH" and "AEDFHR" is "ADH" of length 3.
• LCS for input Sequences "AGGTAB" and "GXTXAYB" is "GTAB" of length 4.

Let‘s break it down into sub-problems:

• Let DP[i][j] be the length of the LCS of strings X[0…i] and Y[0…j]
• If X[i] == Y[j], the LCS of X and Y would be the LCS of X[0…i-1] and Y[0…j-1] plus the common character X[i] or Y[j]
• Else if X[i] != Y[j], we either skip character X[i] or Y[j] and take the maximum

The recurrence relation:

• DP[0][j] = 0 for all j (base case)
• DP[i][0] = 0 for all i (base case)
• DP[i][j] = DP[i-1][j-1] + 1 if X[i]==Y[j]
• DP[i][j] = max(DP[i-1][j], DP[i][j-1]) if X[i] != Y[j]

Here‘s the implementation:

def lcs(X, Y):
m = len(X)
n = len(Y)
DP = [[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]: 
            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]

The time complexity is O(mn) where m and n are the lengths of strings X and Y. The space complexity is O(mn) to store the DP table.

To find the actual longest common subsequence, we can do a traceback. Start at the bottom right cell DP[m][n]. If X[i-1] == Y[j-1], the characters are part of the LCS so include them and move diagonally up to DP[i-1][j-1]. Otherwise, move to the cell with the larger value, either DP[i-1][j] or DP[i][j-1]. Repeat until we reach the top or left edge of the table. The characters included in reverse order will form the LCS.

Tips for Dynamic Programming

• Start by solving the problem recursively. Analyze it for overlapping sub-problems.
• List out the sub-problems and see if you can construct a solution to the original problem from solutions to the sub-problems.
• Decide on state variables to represent the sub-problems. Often 1D or 2D is sufficient but sometimes you may need 3D or more.
• Come up with a recurrence relation to solve a sub-problem given solutions to smaller sub-problems.
• Determine the base cases for the smallest possible sub-problems.
• Work out examples on paper and verify your recurrence relation is correct.
• Code it up, either recursively with memoization or iteratively building a DP table bottom-up.
• Add back pointers or traceback if you need to reconstruct the actual solution and not just the value.

Runtime Analysis of Dynamic Programming

The time complexity of a dynamic programming solution depends on the number of sub-problems and the time to solve each one. With a DP table, this is the number of cells and the recurrence relation within each cell. For example:

• 0/1 Knapsack with n items and capacity W has O(nW) sub-problems, each takes O(1), so total O(nW) time
• Longest common subsequence of strings with lengths m and n has O(mn) sub-problems, each takes O(1), so total O(mn) time

The space complexity is usually the same as time complexity to store the DP table. Sometimes we can optimize space by only storing a few rows or columns of the table if that‘s all that the recurrence relation depends on. For example:

• 0/1 Knapsack space can be optimized to O(W) by storing just 2 rows
• Fibonacci numbers iterative DP only needs O(1) space for the previous 2 numbers

Conclusion

Dynamic programming is a powerful technique to optimize solutions for problems with overlapping sub-problems. The key aspects are:

1. Identify the sub-problems
2. Define a recurrence relation to solve sub-problems
3. Either memoize recursive solution or build DP table bottom-up iteratively

With practice, DP problem patterns will become more recognizable. The techniques in this post should help demystify the core concepts. Start with recursive brute force, identify redundant calculations, then memoize or build a DP table to avoid repeated work. Understand the recurrence relation. Consider optimizing space after getting the solution working.

I hope this post provided a solid introduction to dynamic programming. The best way to master DP is with practice, so go solve some problems on your own now. DP is an essential technique for coding interviews and competitive programming, and a useful tool to have for real-world problems in software engineering.