Dynamic Programming (DP) is an optimization technique that solves problems by breaking them into overlapping subproblems and storing their results to avoid redundant computation.
// DP applies when a problem has:
// 1. Optimal substructure — solution built from subproblem solutions
// 2. Overlapping subproblems — same subproblems solved multiple times
// Without DP: fib(5) recalculates fib(3) multiple times
// With DP: store fib(3) once and reuse
DP transforms exponential-time recursive solutions into polynomial-time solutions.
Memoization (top-down) uses recursion + cache. Tabulation (bottom-up) fills a table iteratively.
// Memoization (top-down)
function fibMemo(n, memo = {}) {
if (n <= 1) return n;
if (memo[n]) return memo[n];
return memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);
}
// Tabulation (bottom-up)
function fibTab(n) {
const dp = [0, 1];
for (let i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
return dp[n];
}
Memoization: easier to write, uses call stack. Tabulation: no stack overhead, often more space-efficient.
Fibonacci with O(n) time and O(1) space by keeping only the last two values:
function fibonacci(n) {
if (n <= 1) return n;
let prev2 = 0, prev1 = 1;
for (let i = 2; i <= n; i++) {
const curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
// fibonacci(10) => 55
This is the space-optimized tabulation approach, reducing from O(n) array to O(1) variables.
You can climb 1 or 2 steps at a time. The number of ways to reach step n equals fib(n+1) because each step is reachable from the previous one or two steps.
function climbStairs(n) {
let a = 1, b = 1;
for (let i = 2; i <= n; i++) {
const temp = a + b;
a = b;
b = temp;
}
return b;
}
// climbStairs(5) => 8
Time: O(n) | Space: O(1)
Find the minimum number of coins needed to make a given amount. Use tabulation with dp[i] = min coins for amount i.
function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (const coin of coins) {
if (coin <= i) dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
// coinChange([1, 5, 10], 11) => 2 (10+1)
Time: O(amount × coins) | Space: O(amount)
Find the length of the longest subsequence common to two strings using a 2D DP table.
function lcs(s1, s2) {
const m = s1.length, n = s2.length;
const dp = Array.from({length: m+1}, () => new Array(n+1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (s1[i-1] === s2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m][n];
}
// lcs("abcde", "ace") => 3
Time: O(m × n) | Space: O(m × n)
Given items with weights and values, find the maximum value you can carry in a knapsack of capacity W. Each item can be taken at most once.
function knapsack(weights, values, W) {
const n = weights.length;
const dp = new Array(W + 1).fill(0);
for (let i = 0; i < n; i++) {
for (let w = W; w >= weights[i]; w--) {
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[W];
}
// knapsack([2,3,4], [3,4,5], 5) => 7
Time: O(n × W) | Space: O(W) with 1D optimization
Find the length of the longest strictly increasing subsequence. The O(n log n) approach uses a tails array with binary search.
function lis(arr) {
const tails = [];
for (const num of arr) {
let lo = 0, hi = tails.length;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (tails[mid] < num) lo = mid + 1;
else hi = mid;
}
tails[lo] = num;
}
return tails.length;
}
// lis([10, 9, 2, 5, 3, 7, 101, 18]) => 4
Time: O(n log n) | Space: O(n)
Edit Distance (Levenshtein distance) finds the minimum operations (insert, delete, replace) to convert one string to another.
function editDistance(s1, s2) {
const m = s1.length, n = s2.length;
const dp = Array.from({length: m+1}, (_, i) =>
Array.from({length: n+1}, (_, j) => i === 0 ? j : j === 0 ? i : 0)
);
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (s1[i-1] === s2[j-1]) dp[i][j] = dp[i-1][j-1];
else dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
}
}
return dp[m][n];
}
// editDistance("kitten", "sitting") => 3
Time: O(m × n) | Space: O(m × n)
Matrix Chain Multiplication finds the optimal way to parenthesize matrix multiplications to minimize total scalar multiplications.
function matrixChain(dims) {
const n = dims.length - 1;
const dp = Array.from({length: n}, () => new Array(n).fill(0));
for (let len = 2; len <= n; len++) {
for (let i = 0; i <= n - len; i++) {
const j = i + len - 1;
dp[i][j] = Infinity;
for (let k = i; k < j; k++) {
const cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1];
dp[i][j] = Math.min(dp[i][j], cost);
}
}
}
return dp[0][n - 1];
}
// matrixChain([10, 20, 30, 40]) => 18000
Time: O(n³) | Space: O(n²)
Build a 1D DP array where dp[i] = minimum coins needed for amount i. For each coin, update all reachable amounts.
function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (const coin of coins) {
if (coin <= i && dp[i - coin] + 1 < dp[i]) {
dp[i] = dp[i - coin] + 1;
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
// Input: coins=[1,5,11], amount=15 => Output: 3 (5+5+5)
// Input: coins=[2], amount=3 => Output: -1 (impossible)
// Input: coins=[1,2,5], amount=11 => Output: 3 (5+5+1)
Time: O(amount × coins) | Space: O(amount)
2D DP: dp[i][w] = max value using first i items with weight limit w. Either skip item i or include it (if it fits).
function knapsack(weights, values, capacity) {
const n = weights.length;
const dp = Array.from({length: n+1}, () => new Array(capacity+1).fill(0));
for (let i = 1; i <= n; i++) {
for (let w = 0; w <= capacity; w++) {
dp[i][w] = dp[i-1][w]; // skip item i
if (weights[i-1] <= w) {
dp[i][w] = Math.max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1]);
}
}
}
return dp[n][capacity];
}
// weights=[1,3,4,5], values=[1,4,5,7], capacity=7
// Output: 9 (items with weight 3 and 4, values 4+5)
Time: O(n × W) | Space: O(n × W), can be optimized to O(W)
dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]. If characters match, extend from dp[i-1][j-1]; otherwise take max of dp[i-1][j] and dp[i][j-1].
function longestCommonSubsequence(text1, text2) {
const m = text1.length, n = text2.length;
const dp = Array.from({length: m+1}, () => new Array(n+1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (text1[i-1] === text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m][n];
}
// Input: text1="abcde", text2="ace" => Output: 3 ("ace")
// Input: text1="abc", text2="abc" => Output: 3
// Input: text1="abc", text2="def" => Output: 0
Time: O(m × n) | Space: O(m × n)
dp[i][j] = min operations to convert word1[0..i-1] to word2[0..j-1]. Operations: insert, delete, replace. If chars match: no cost; otherwise 1 + min of three operations.
function minDistance(word1, word2) {
const m = word1.length, n = word2.length;
const dp = Array.from({length: m+1}, (_, i) => Array.from({length: n+1}, (_, j) => i || j));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1[i-1] === word2[j-1]) dp[i][j] = dp[i-1][j-1];
else dp[i][j] = 1 + Math.min(
dp[i-1][j], // delete from word1
dp[i][j-1], // insert into word1
dp[i-1][j-1] // replace
);
}
}
return dp[m][n];
}
// Input: word1="horse", word2="ros" => Output: 3
// Input: word1="intention", word2="execution" => Output: 5
Time: O(m × n) | Space: O(m × n), can be O(n)
DP where dp[i] = number of ways to decode s[0..i-1]. Take one digit (valid if non-zero) or two digits (valid if 10-26). Add values from valid positions.
function numDecodings(s) {
if (!s || s[0] === '0') return 0;
const n = s.length;
const dp = new Array(n + 1).fill(0);
dp[0] = 1; dp[1] = 1;
for (let i = 2; i <= n; i++) {
const one = Number(s[i-1]);
const two = Number(s.slice(i-2, i));
if (one >= 1) dp[i] += dp[i-1]; // single digit
if (two >= 10 && two <= 26) dp[i] += dp[i-2]; // two digits
}
return dp[n];
}
// Input: "12" => Output: 2 ("AB"=1,2 or "L"=12)
// Input: "226" => Output: 3 ("BZ","VF","BBF")
// Input: "06" => Output: 0 (leading zero, invalid)
Time: O(n) | Space: O(n), can be O(1)
DP: dp[i] = length of LIS ending at index i. For each i, check all j < i where arr[j] < arr[i]. Patience sort / binary search gives O(n log n).
// O(n²) DP:
function lengthOfLIS(nums) {
const dp = new Array(nums.length).fill(1);
let best = 1;
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
best = Math.max(best, dp[i]);
}
return best;
}
// O(n log n) — patience sort with binary search:
function lengthOfLISFast(nums) {
const tails = [];
for (const n of nums) {
let lo = 0, hi = tails.length;
while (lo < hi) { const m = (lo+hi)>>1; if (tails[m]<n) lo=m+1; else hi=m; }
tails[lo] = n;
}
return tails.length;
}
// Input: [10,9,2,5,3,7,101,18] => Output: 4 ([2,3,7,101])
// Input: [0,1,0,3,2,3] => Output: 4
Time: O(n²) DP | O(n log n) patience sort | Space: O(n)
At each house, either rob it (prev_prev + current) or skip it (keep prev). No need for 2D DP — two variables suffice.
function rob(nums) {
let prev2 = 0, prev1 = 0;
for (const n of nums) {
const curr = Math.max(prev1, prev2 + n);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
// Input: [1,2,3,1] => Output: 4 (rob house 1 and 3)
// Input: [2,7,9,3,1] => Output: 12 (rob houses 1,3,5)
// Input: [2,1] => Output: 2
// Circular variant (House Robber II): run twice
// Once on [0..n-2], once on [1..n-1], take max
Time: O(n) | Space: O(1)
DP: dp[j] = can we make sum j using a subset? Iterate backwards to prevent reuse (0/1 knapsack style).
function canPartition(nums) {
const total = nums.reduce((a, b) => a + b, 0);
if (total % 2 !== 0) return false; // odd total can't split evenly
const target = total / 2;
const dp = new Array(target + 1).fill(false);
dp[0] = true;
for (const num of nums) {
for (let j = target; j >= num; j--) {
dp[j] = dp[j] || dp[j - num]; // can add num to reach j
}
}
return dp[target];
}
// Input: [1,5,11,5] => Output: true ([1,5,5] and [11])
// Input: [1,2,3,5] => Output: false
// Input: [14,9,8,4,3,2] => Output: true
Time: O(n × target) | Space: O(target)
Similar to LCS but reset on mismatch. dp[i][j] = length of longest common substring ending at text1[i-1] and text2[j-1].
function longestCommonSubstring(s1, s2) {
const m = s1.length, n = s2.length;
const dp = Array.from({length: m+1}, () => new Array(n+1).fill(0));
let maxLen = 0;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (s1[i-1] === s2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
maxLen = Math.max(maxLen, dp[i][j]);
}
}
}
return maxLen;
}
// Input: s1="ABCBDAB", s2="BDCAB" => Output: 2 ("AB" or "BD")
// Input: s1="abcde", s2="abfce" => Output: 2 ("ab")
Time: O(m × n) | Space: O(m × n)
DP with states: transaction count and hold/not-hold. dp[k][0] = max profit after k transactions with no stock held. dp[k][1] = max profit holding a stock.
function maxProfit(k, prices) {
const n = prices.length;
if (k >= Math.floor(n / 2)) {
// Unlimited transactions: just take all up-slopes
let profit = 0;
for (let i = 1; i < n; i++) profit += Math.max(0, prices[i] - prices[i-1]);
return profit;
}
const dp = Array.from({length: k+1}, () => [0, -Infinity]);
for (const price of prices) {
for (let t = k; t >= 1; t--) {
dp[t][0] = Math.max(dp[t][0], dp[t][1] + price); // sell
dp[t][1] = Math.max(dp[t][1], dp[t-1][0] - price); // buy
}
}
return dp[k][0];
}
// Input: k=2, prices=[3,2,6,5,0,3] => Output: 7 (buy@2 sell@6, buy@0 sell@3)
// Input: k=1, prices=[3,2,6,5,0,3] => Output: 4 (buy@2 sell@6)
Time: O(n × k) | Space: O(k)
DP with two passes: precompute a palindrome table, then find minimum cuts needing dp[i] cuts for s[0..i] where s[j+1..i] is a palindrome.
function minCut(s) {
const n = s.length;
// isPalin[i][j] = is s[i..j] palindrome?
const isPalin = Array.from({length: n}, () => new Array(n).fill(false));
for (let i = n-1; i >= 0; i--) {
for (let j = i; j < n; j++) {
if (s[i] === s[j] && (j - i <= 2 || isPalin[i+1][j-1])) {
isPalin[i][j] = true;
}
}
}
const dp = new Array(n).fill(0).map((_, i) => i); // worst case: cut every char
for (let i = 1; i < n; i++) {
if (isPalin[0][i]) { dp[i] = 0; continue; } // whole prefix is palindrome
for (let j = 1; j <= i; j++) {
if (isPalin[j][i]) dp[i] = Math.min(dp[i], dp[j-1] + 1);
}
}
return dp[n-1];
}
// Input: "aab" => Output: 1 ("aa" | "b")
// Input: "a" => Output: 0 (no cut needed)
// Input: "ab" => Output: 1 ("a" | "b")
Time: O(n²) | Space: O(n²)
dp[i] = can s[0..i-1] be segmented using the dictionary? For each i, check all j < i where dp[j] is true and s[j..i-1] is in the word set.
function wordBreak(s, wordDict) {
const wordSet = new Set(wordDict);
const dp = new Array(s.length + 1).fill(false);
dp[0] = true; // empty string
for (let i = 1; i <= s.length; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && wordSet.has(s.slice(j, i))) {
dp[i] = true;
break; // optimization
}
}
}
return dp[s.length];
}
// Input: s="leetcode", wordDict=["leet","code"] => Output: true
// Input: s="applepenapple", wordDict=["apple","pen"] => Output: true
// Input: s="catsandog", wordDict=["cats","dog","sand","and","cat"] => Output: false
Time: O(n² × m) where m = avg word length | Space: O(n)