Dynamic Programming
A method for solving complex problems by breaking them down into simpler subproblems and storing their solutions to avoid redundant computations.
Dynamic Programming
Dynamic Programming (DP) is a technique for solving complex problems by breaking them down into simpler overlapping subproblems and storing the solutions to these subproblems to avoid redundant calculation. It's particularly useful for optimization problems where the goal is to find the best solution among many possible options.
Two key properties typically characterize problems suited for dynamic programming:
- Optimal substructure: An optimal solution to the problem contains optimal solutions to its subproblems
- Overlapping subproblems: The same subproblems are encountered multiple times when solving the problem
Dynamic programming can be implemented using two main approaches:
- Top-down (memoization): Start with the original problem, break it into subproblems, and store their solutions as they're computed
- Bottom-up (tabulation): Start by solving the smallest subproblems first, then use their solutions to build up to larger problems
The primary advantage of dynamic programming is that it can dramatically improve the efficiency of algorithms for problems with overlapping subproblems, often reducing exponential time complexity to polynomial time.
Examples
- Fibonacci sequence calculation with memoization
- Knapsack problem: Finding the most valuable combination of items that fit within a weight constraint
- Longest Common Subsequence: Finding the longest sequence common to two sequences
- Shortest path algorithms like Floyd-Warshall
Code Example
// Fibonacci using dynamic programming (memoization)
function fibonacciDP(n, memo = {}) {
// Check if we've already computed this value
if (n in memo) return memo[n];
// Base cases
if (n <= 0) return 0;
if (n === 1) return 1;
// Store and return the result
memo[n] = fibonacciDP(n - 1, memo) + fibonacciDP(n - 2, memo);
return memo[n];
}
// Fibonacci using dynamic programming (tabulation)
function fibonacciTabulation(n) {
if (n <= 0) return 0;
if (n === 1) return 1;
// Create an array to store values
const dp = new Array(n + 1);
dp[0] = 0;
dp[1] = 1;
// Fill the array
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}Related Terms
Further Learning
Want to see these concepts in action?