Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit5497597

Browse files
committed
Add bottom-up dynamic programming solution to Jump Game.
1 parent57c2a33 commit5497597

File tree

5 files changed

+89
-5
lines changed

5 files changed

+89
-5
lines changed
Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
importdpBottomUpJumpGamefrom'../dpBottomUpJumpGame';
2+
3+
describe('dpBottomUpJumpGame',()=>{
4+
it('should solve Jump Game problem in bottom-up dynamic programming manner',()=>{
5+
expect(dpBottomUpJumpGame([1,0])).toBeTruthy();
6+
expect(dpBottomUpJumpGame([100,0])).toBeTruthy();
7+
expect(dpBottomUpJumpGame([2,3,1,1,4])).toBeTruthy();
8+
expect(dpBottomUpJumpGame([1,1,1,1,1])).toBeTruthy();
9+
expect(dpBottomUpJumpGame([1,1,1,10,1])).toBeTruthy();
10+
expect(dpBottomUpJumpGame([1,5,2,1,0,2,0])).toBeTruthy();
11+
12+
expect(dpBottomUpJumpGame([1,0,1])).toBeFalsy();
13+
expect(dpBottomUpJumpGame([3,2,1,0,4])).toBeFalsy();
14+
expect(dpBottomUpJumpGame([0,0,0,0,0])).toBeFalsy();
15+
expect(dpBottomUpJumpGame([5,4,3,2,1,0,0])).toBeFalsy();
16+
});
17+
});

‎src/algorithms/uncategorized/jump-game/backtrackingJumpGame.js

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,12 @@
11
/**
22
* BACKTRACKING approach of solving Jump Game.
33
*
4+
* This is the inefficient solution where we try every single jump
5+
* pattern that takes us from the first position to the last.
6+
* We start from the first position and jump to every index that
7+
* is reachable. We repeat the process until last index is reached.
8+
* When stuck, backtrack.
9+
*
410
*@param {number[]} numbers - array of possible jump length.
511
*@param {number} startIndex - index from where we start jumping.
612
*@param {number[]} currentJumps - current jumps path.
Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
/**
2+
* DYNAMIC PROGRAMMING BOTTOM-UP approach of solving Jump Game.
3+
*
4+
* This comes out as an optimisation of DYNAMIC PROGRAMMING TOP-DOWN approach.
5+
*
6+
* The observation to make here is that we only ever jump to the right.
7+
* This means that if we start from the right of the array, every time we
8+
* will query a position to our right, that position has already be
9+
* determined as being GOOD or BAD. This means we don't need to recurse
10+
* anymore, as we will always hit the memo table.
11+
*
12+
* We call a position in the array a "good" one if starting at that
13+
* position, we can reach the last index. Otherwise, that index
14+
* is called a "bad" one.
15+
*
16+
*@param {number[]} numbers - array of possible jump length.
17+
*@return {boolean}
18+
*/
19+
exportdefaultfunctiondpBottomUpJumpGame(numbers){
20+
// Init cells goodness table.
21+
constcellsGoodness=Array(numbers.length).fill(undefined);
22+
// Mark the last cell as "good" one since it is where we ultimately want to get.
23+
cellsGoodness[cellsGoodness.length-1]=true;
24+
25+
// Go throw all cells starting from the one before the last
26+
// one (since the last one is "good" already) and fill cellsGoodness table.
27+
for(letcellIndex=numbers.length-2;cellIndex>=0;cellIndex-=1){
28+
constmaxJumpLength=Math.min(
29+
numbers[cellIndex],
30+
numbers.length-1-cellIndex,
31+
);
32+
33+
for(letjumpLength=maxJumpLength;jumpLength>0;jumpLength-=1){
34+
constnextIndex=cellIndex+jumpLength;
35+
if(cellsGoodness[nextIndex]===true){
36+
cellsGoodness[cellIndex]=true;
37+
// Once we detected that current cell is good one we don't need to
38+
// do further cells checking.
39+
break;
40+
}
41+
}
42+
}
43+
44+
// Now, if the zero's cell is good one then we can jump from it to the end of the array.
45+
returncellsGoodness[0]===true;
46+
}

‎src/algorithms/uncategorized/jump-game/dpTopDownJumpGame.js

Lines changed: 7 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -2,11 +2,14 @@
22
* DYNAMIC PROGRAMMING TOP-DOWN approach of solving Jump Game.
33
*
44
* This comes out as an optimisation of BACKTRACKING approach.
5-
* Optimisation is done by using memo table where we store information
6-
* about each cell whether it is "good" or "bad" or "unknown".
5+
*
6+
* It relies on the observation that once we determine that a certain
7+
* index is good / bad, this result will never change. This means that
8+
* we can store the result and not need to recompute it every time.
79
*
810
* We call a position in the array a "good" one if starting at that
9-
* position, we can reach the last index.
11+
* position, we can reach the last index. Otherwise, that index
12+
* is called a "bad" one.
1013
*
1114
*@param {number[]} numbers - array of possible jump length.
1215
*@param {number} startIndex - index from where we start jumping.
@@ -30,8 +33,7 @@ export default function dpTopDownJumpGame(
3033
constcurrentCellsGoodness=[...cellsGoodness];
3134
if(!currentCellsGoodness.length){
3235
numbers.forEach(()=>currentCellsGoodness.push(undefined));
33-
// Mark the last cell as "good" one since it is where
34-
// we ultimately want to get.
36+
// Mark the last cell as "good" one since it is where we ultimately want to get.
3537
currentCellsGoodness[cellsGoodness.length-1]=true;
3638
}
3739

‎src/algorithms/uncategorized/jump-game/greedyJumpGame.js

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,19 @@
11
/**
22
* GREEDY approach of solving Jump Game.
33
*
4+
* This comes out as an optimisation of DYNAMIC PROGRAMMING BOTTOM_UP approach.
5+
*
6+
* Once we have our code in the bottom-up state, we can make one final,
7+
* important observation. From a given position, when we try to see if
8+
* we can jump to a GOOD position, we only ever use one - the first one.
9+
* In other words, the left-most one. If we keep track of this left-most
10+
* GOOD position as a separate variable, we can avoid searching for it
11+
* in the array. Not only that, but we can stop using the array altogether.
12+
*
13+
* We call a position in the array a "good" one if starting at that
14+
* position, we can reach the last index. Otherwise, that index
15+
* is called a "bad" one.
16+
*
417
*@param {number[]} numbers - array of possible jump length.
518
*@return {boolean}
619
*/

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp