[数据结构与算法]力扣55题-- 跳跃游戏

个人博客：https://thiswhl.cn

方法一：动态规划

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    //动态规划dp
    const totalLength = nums.length
    const memo = Array(totalLength).fill(0)
    memo[totalLength - 1] = 1;

    function jump(position){
        if(memo[position] === 1){
            return true;
        }
        else if(memo[position] === -1){
            return false;
        }
        const maxJump = Math.min(position+nums[position],totalLength-1)
        for(let i = position+1;i<=maxJump;i++){
            const jumpResult = jump(i)
            if(jumpResult == true){
                memo[position] = 1
                return true
            }
        }
        memo[position] = -1
        return false;
    }
    
    let result = jump(0)
    return result

};

方法二:bottom-up

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    //贪心
    const totalLength = nums.length;
    const memo = Array(totalLength).fill(0)

    memo[totalLength-1] = 1;

    for(let i = totalLength - 2;i>=0;i--){
        const maxJump = Math.min(i + nums[i],totalLength-1)
        for(let j = i+1;j<=maxJump;j++){
            if(memo[j] === 1){
                memo[i]=1
                break;
            }
        }
    }
    if(memo[0] === 1){
        return true
    }else{
        return false;
    }
};

方法三（最简单）:贪心

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    //贪心
    let maxJump = nums.length - 1
    for(let i = nums.length - 2;i>=0;i--){
        if(i+nums[i]>=maxJump){
            maxJump = i
        }
    }
    return maxJump === 0
};