Overview
Dynamic Programming (DP) is an optimization technique used to solve complex problems by breaking them down into simpler, overlapping subproblems and storing the results of these subproblems to avoid redundant calculations.
Core Concepts
- Optimal Substructure: A problem has optimal substructure if the optimal solution to the problem contains optimal solutions to its subproblems.
- Overlapping Subproblems: The same subproblems are solved multiple times during the computation.
- Approaches:
- Top-Down (Memoization): Start with the original problem and recursively break it down. Store the result of each subproblem in a cache (e.g., a hash map).
- Bottom-Up (Tabulation): Solve the smallest subproblems first and use their results to build up to the solution of the original problem, usually using a table (array).
- State: The set of variables that uniquely describe a subproblem.
- State Transition Equation: The mathematical formula that defines how to solve a problem based on its subproblems.
Code Examples
// Fibonacci: Top-Down with Memoization
const memo: Record<number, number> = {};
function fibMemo(n: number): number {
if (n <= 1) return n;
if (n in memo) return memo[n];
memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
return memo[n];
}
// Fibonacci: Bottom-Up with Tabulation
function fibTab(n: number): number {
if (n <= 1) return n;
const dp = new Array(n + 1);
dp[0] = 0;
dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}Use Cases
- Shortest Path Algorithms: Bellman-Ford or Floyd-Warshall.
- Resource Allocation: The Knapsack Problem.
- Sequence Alignment: Edit distance (Levenshtein) or Longest Common Subsequence (LCS).
Gotchas
- Space Complexity: DP often trades space for time. Using a large table can lead to memory issues.
- Incorrect State Definition: If the “state” doesn’t capture all necessary information, the transition equation will be wrong.
- Recursion Depth: Top-down approaches can hit the maximum call stack limit for very deep problems.