Break a problem into smaller overlapping problems, solve each one once and store the result so it is never recomputed.
Used for
ways[0] = 1, ways[1] = 1
1 + 1 = 2
2 + 1 = 3
5 + 3 = 8
Following the same rule, what is ways[6]?
Not quite. ways[6] = ways[5] + ways[4] = 8 + 5 = 13.
Step 1 of 6
Goal: how many ways can you climb 5 stairs taking 1 or 2 steps at a time? You reach stair 5 from stair 4 or stair 3, so ways(5) = ways(4) + ways(3). Working that out naively repeats the same sub-questions many times. Instead write each answer down once.
Step 2 of 6
Base cases: there is 1 way to be on stair 0 (do nothing) and 1 way to reach stair 1.
Step 3 of 6
Stair 2 is reached from stair 1 or stair 0.
Step 4 of 6
Stair 3 comes from stairs 2 and 1.
Step 5 of 6
Stair 4: 3 + 2 = 5. Stair 5: 5 + 3 = 8. Each answer reuses two stored answers, so n stairs take n steps instead of exponential time. Storing sub-answers like this is dynamic programming.
Step 6 of 6
Your turn.
MemoizationRecursionTravelling Salesman ProblemMaximum subarray problemUnique Paths ProblemBest Time to Buy and Sell StockLongest Increasing SubsequenceShortest Common SupersequenceFibonacci NumberInteger PartitionLongest Common Substring ProblemRegular Expression MatchingRecursive Staircase ProblemKnapsack ProblemLongest common subsequence problemLevenshtein Distance
function coinChange(coins, amount) { const dp = Array(amount + 1).fill(Infinity); dp[0] = 0; for (let a = 1; a <= amount; a++) for (const c of coins) if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1); return dp[amount] === Infinity ? -1 : dp[amount];}