[Leetcode][JavaScript] 55. Jump Game

1. DP solution

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    let i=nums.length-1;
    const jumps= new Array(nums.length).fill(false);
    jumps[i]=true;
    
    for (;i>=0;i--){
        let max = Math.min(i+nums[i], nums.length-1)
        
        for(let j=i; max>=j;j++){
            if(jumps[j]){
                jumps[i]=true;
            }
        }
    }
    return jumps[0]
};

2. Greedy Solution

var canJump = function(nums) {
    let index=nums.length-1;
  
    
    for (let i= index-1 ;i>=0;i--){
        if(index<= i+nums[i]){
            index=i;
        }
    }
    return index===0
};

Greedy로 풀기 위해서는 jumps들의 상태를 기억할 필요가 없음을 기억하자. Greedy에서는 current State만 기억할 수 있으면 된다.