Dynamic programming

When Can We Use DP?

DP is applicable when a problem has two key attributes:

1. Overlapping Subproblems: A problem has overlapping subproblems if finding its solution involves solving the same subproblems multiple times. DP solves each subproblem just once and stores its result to avoid re-computation.
2. Optimal Substructure: A problem exhibits optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems.

A Motivating Example: Coin Problem

Problem: What is the minimum number of coins required to make change for an amount x, given a set of coin denominations {c₁, c₂, ...}?

A greedy approach doesn't always work here. But we can define a DP state. Let dp[i] be the minimum number of coins to make amount i.
The base case is dp[0] = 0.
For any other amount i, the solution is built from smaller solutions. To make amount i, we must have used a last coin, say c_j. The number of coins would then be dp[i - c_j] + 1. We want the minimum over all possible last coins.
Transition: dp[i] = min(dp[i - c_j] + 1) for all coins c_j <= i.

Two Main DP Approaches

1. Memoization (Top-Down):

This is a recursive approach. You write a standard recursive function for the problem. Then, you "memoize" the results of each subproblem in a lookup table (e.g., an array or hash map). Before computing a subproblem, you check if the result is already in the table. If so, use it. Otherwise, compute it, store it, and then return it.

# Python: Fibonacci with Memoization
memo = {}
def fib(n):
  if n <= 1: return n
  if n in memo: return memo[n]
result = fib(n-1) + fib(n-2)
memo[n] = result
return result

2. Tabulation (Bottom-Up):

This is an iterative approach. You solve the problem "bottom-up" by first solving all the smallest subproblems. You then use these results to solve larger and larger subproblems until you have solved the original problem. This is typically done by filling out a DP table (usually a 1D or 2D array) in a specific order.

# Python: Fibonacci with Tabulation
def fib(n):
  dp = [0] * (n + 1)
  if n >= 1: dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]

Classic DP Problems

• Fibonacci Sequence / Climbing Stairs
• Longest Common Subsequence (LCS)
• 0/1 Knapsack Problem & Unbounded Knapsack
• Coin Change Problem
• Longest Increasing Subsequence (LIS)
• Edit Distance