← Data structures from scratch · Lesson 32/32
Dynamic programming: never compute twice
The same work, over and over
How many ways can you climb a staircase of n steps taking 1 or 2 at a time? To reach step n you come from n-1 or n-2, so formas(n) = formas(n-1) + formas(n-2).
The direct recursion is correct but terribly slow: formas(n-2) gets computed inside formas(n-1) and again outside, and so on down. The calls grow like O(2ⁿ). Count how many it makes:
$ node leccion.js
Press RUN (or Ctrl+Enter).
What to look at
With 25 steps there are 121,393 ways, but almost 243,000 calls: every small result gets recomputed thousands of times. Every 5 extra steps, the calls multiply by 11.
The whole lesson on one page
The same work, over and over
How many ways can you climb a staircase of n steps taking 1 or 2 at a time? To reach step n you come from n-1 or n-2, so formas(n) = formas(n-1) + formas(n-2).
The direct recursion is correct but terribly slow: formas(n-2) gets computed inside formas(n-1) and again outside, and so on down. The calls grow like O(2ⁿ). Count how many it makes:
let llamadas = 0;
function formas(n) {
llamadas++;
if (n <= 1) return 1;
return formas(n - 1) + formas(n - 2);
}
for (const n of [10, 20, 25]) {
llamadas = 0;
const r = formas(n);
console.log(n, "escalones:", r, "formas,", llamadas, "llamadas");
}
With 25 steps there are 121,393 ways, but almost 243,000 calls: every small result gets recomputed thousands of times. Every 5 extra steps, the calls multiply by 11.
Memoization: write it down before you forget
Dynamic programming means solving a problem with repeating subproblems by storing each answer the first time. The most direct way is memoization: before computing, check whether you already have it in a Map; if not, compute it and write it down.
Now each n is computed only once: O(n). What would have taken weeks without it comes out instantly.
function formasMemo(n, memo = new Map()) {
if (n <= 1) return 1;
if (memo.has(n)) return memo.get(n);
const r = formasMemo(n - 1, memo) + formasMemo(n - 2, memo);
memo.set(n, r);
return r;
}
console.log(formasMemo(25));
console.log(formasMemo(70));
25 gives the same as before, and 70 comes out immediately: 308,061,521,170,129 ways. Without the memo, it would take some 600 trillion calls.
The table, bottom-up
The other way is to fill a table from the smallest case up to the one you want, with no recursion. The coin challenge: what's the minimum number of coins that add up to an amount?
dp[m] is the minimum for amount m. dp[0] = 0, and for each m you try each coin c: dp[m - c] + 1. With coins of 1, 3 and 4 and an amount of 6, the answer is 2 (3 + 3). Always taking the biggest coin would give 4 + 1 + 1, three coins: that's why the "greedy" shortcut doesn't work here and you need the table.
The usual recipe: state (what dp[m] means), transition (how it comes from earlier ones), base case, and filling order.
function minMonedas(monedas, monto) {
const dp = new Array(monto + 1).fill(Infinity);
dp[0] = 0;
for (let m = 1; m <= monto; m++) {
for (const c of monedas) {
if (c <= m && dp[m - c] + 1 < dp[m]) dp[m] = dp[m - c] + 1;
}
}
console.log(dp);
return dp[monto] === Infinity ? -1 : dp[monto];
}
console.log(minMonedas([1, 3, 4], 6));
console.log(minMonedas([5, 10], 3));
- The table for
[1, 3, 4]is the one in the drawing: 6 is filled from 3 (dp[3] + 1 = 2). - With 5 and 10 coins there's no way to make 3: the table stays at
Infinityand the function returns -1.
Sometimes the table fits in two variables
If each cell depends only on the previous one, you don't need to keep the whole table. Kadane's algorithm finds the contiguous subarray with the largest sum: at each position you decide whether to extend the stretch you had or start a new one here, and you remember the best one you've seen.
It's dynamic programming in O(n) time and O(1) memory.
function mayorSubarreglo(nums) {
let actual = nums[0], mejor = nums[0];
for (let i = 1; i < nums.length; i++) {
actual = Math.max(nums[i], actual + nums[i]);
mejor = Math.max(mejor, actual);
}
return mejor;
}
console.log(mayorSubarreglo([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
console.log(mayorSubarreglo([-3, -1, -2]));
- The 6 comes from the stretch
[4, -1, 2, 1]: the -1 isn't enough to break it. - If everything is negative, the best stretch is the least bad number, -1.