|
| 1 | +/** |
| 2 | + * DYNAMIC PROGRAMMING TOP-DOWN approach of solving Jump Game. |
| 3 | + * |
| 4 | + * 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". |
| 7 | + * |
| 8 | + * We call a position in the array a "good" one if starting at that |
| 9 | + * position, we can reach the last index. |
| 10 | + * |
| 11 | + *@param {number[]} numbers - array of possible jump length. |
| 12 | + *@param {number} startIndex - index from where we start jumping. |
| 13 | + *@param {number[]} currentJumps - current jumps path. |
| 14 | + *@param {boolean[]} cellsGoodness - holds information about whether cell is "good" or "bad" |
| 15 | + *@return {boolean} |
| 16 | + */ |
| 17 | +exportdefaultfunctiondpTopDownJumpGame( |
| 18 | +numbers, |
| 19 | +startIndex=0, |
| 20 | +currentJumps=[], |
| 21 | +cellsGoodness=[], |
| 22 | +){ |
| 23 | +if(startIndex===numbers.length-1){ |
| 24 | +// We've jumped directly to last cell. This situation is a solution. |
| 25 | +returntrue; |
| 26 | +} |
| 27 | + |
| 28 | +// Init cell goodness table if it is empty. |
| 29 | +// This is DYNAMIC PROGRAMMING feature. |
| 30 | +constcurrentCellsGoodness=[...cellsGoodness]; |
| 31 | +if(!currentCellsGoodness.length){ |
| 32 | +numbers.forEach(()=>currentCellsGoodness.push(undefined)); |
| 33 | +// Mark the last cell as "good" one since it is where |
| 34 | +// we ultimately want to get. |
| 35 | +currentCellsGoodness[cellsGoodness.length-1]=true; |
| 36 | +} |
| 37 | + |
| 38 | +// Check what the longest jump we could make from current position. |
| 39 | +// We don't need to jump beyond the array. |
| 40 | +constmaxJumpLength=Math.min( |
| 41 | +numbers[startIndex],// Jump is within array. |
| 42 | +numbers.length-1-startIndex,// Jump goes beyond array. |
| 43 | +); |
| 44 | + |
| 45 | +// Let's start jumping from startIndex and see whether any |
| 46 | +// jump is successful and has reached the end of the array. |
| 47 | +for(letjumpLength=maxJumpLength;jumpLength>0;jumpLength-=1){ |
| 48 | +// Try next jump. |
| 49 | +constnextIndex=startIndex+jumpLength; |
| 50 | + |
| 51 | +// Jump only into "good" or "unknown" cells. |
| 52 | +// This is top-down dynamic programming optimisation of backtracking algorithm. |
| 53 | +if(currentCellsGoodness[nextIndex]!==false){ |
| 54 | +currentJumps.push(nextIndex); |
| 55 | + |
| 56 | +constisJumpSuccessful=dpTopDownJumpGame( |
| 57 | +numbers, |
| 58 | +nextIndex, |
| 59 | +currentJumps, |
| 60 | +currentCellsGoodness, |
| 61 | +); |
| 62 | + |
| 63 | +// Check if current jump was successful. |
| 64 | +if(isJumpSuccessful){ |
| 65 | +returntrue; |
| 66 | +} |
| 67 | + |
| 68 | +// BACKTRACKING. |
| 69 | +// If previous jump wasn't successful then retreat and try the next one. |
| 70 | +currentJumps.pop(); |
| 71 | + |
| 72 | +// Mark current cell as "bad" to avoid its deep visiting later. |
| 73 | +currentCellsGoodness[nextIndex]=false; |
| 74 | +} |
| 75 | +} |
| 76 | + |
| 77 | +returnfalse; |
| 78 | +} |