Easy Problemsminimizationlinear

Jump Game

Given an array where each value is the farthest a jump from that position can reach, and starting at the first index, find the minimum number of jumps needed to reach the last index.

Do this lesson first: coin change

Example input

nums = [2, 1, 2, 1, 1, 3, 1, 1, 1]

Expected output

4

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i] = 1 + min over j < i with j + nums[j] >= i of dp[j]

Ask where the jump that landed on i came from. It came from some earlier index j, and the jump was legal only if j's own reach, j + nums[j], stretches to i or beyond. Whatever that j was, getting to it optimally is the same problem on a shorter prefix, so the cost is dp[j] plus the one jump you just took. Take the cheapest j among the legal ones. If no j reaches i at all, nothing lands there, ever.

dp[0] = 0: you start on index 0, so it takes no jumps to be there. Fill left to right, because every j the recurrence reads is strictly smaller than i. Some cells have no legal j whatsoever, and those are unreachable, written as an infinity rather than a zero. In this array index 9 holds a 0, a dead end, and nothing before it reaches past index 9, so indices 10 and beyond can never be landed on no matter how large the table grows.

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[0] = 0: you start on index 0, so it takes no jumps to be there. Fill left to right, because every j the recurrence reads is strictly smaller than i. Some cells have no legal j whatsoever, and those are unreachable, written as an infinity rather than a zero. In this array index 9 holds a 0, a dead end, and nothing before it reaches past index 9, so indices 10 and beyond can never be landed on no matter how large the table grows.

i=0

i=1

i=2

i=3

i=4

i=5

i=6

i=7

i=8

0

1

2

3

4

jump-game.ts

1function minJumps(nums) {
2 const dp = [0];
3 for (let i = 1; i < nums.length; i++) {
4 dp[i] = Infinity;
5 for (let j = 0; j < i; j++) {
6 if (j + nums[j] >= i) {
7 dp[i] = Math.min(dp[i], dp[j] + 1);
8 }
9 }
10 }
11 return dp[nums.length - 1];
12}

Base caseComputedBeing readAnswer

The code, the trap, the variations

jump-game.ts

1function minJumps(nums) {
2 const dp = [0];
3 for (let i = 1; i < nums.length; i++) {
4 dp[i] = Infinity;
5 for (let j = 0; j < i; j++) {
6 if (j + nums[j] >= i) {
7 dp[i] = Math.min(dp[i], dp[j] + 1);
8 }
9 }
10 }
11 return dp[nums.length - 1];
12}

Where people go wrong

Treating an unreachable index as costing zero jumps. An empty minimum is not 0, it is infinity, and if you seed the cell with 0 the whole table downstream reads as reachable in one cheap hop. The second trap is reading nums[i] as an exact jump length rather than a maximum reach. Every index strictly between j and j + nums[j] is a legal landing spot, which is precisely why one large value can flatten several cells to the same count.

You only need to know whether the last index is reachable at all, not how few jumps it takes.
The cell becomes a boolean and the recurrence becomes an or over the same j. That version has a one-pass greedy solution: track the farthest reach seen so far and fail the moment your position passes it.
Each index carries a cost to jump from, and you want the cheapest total rather than the fewest jumps.
Only the 1 changes, into cost[j]. The shape of the recurrence is untouched, which is the useful thing to notice: fewest-of-something and cheapest-of-something are the same table with a different increment.

Cutting a Rod Longest Common Substring