leecode:45.跳跃游戏

1.题目描述

2.问题分析

跳跃问题的关键点在于当前能跳跃的步长，和下一步能跳的长度，据此建模：当前数组值为能跳的最大步数，遍历可跳的所有步数，再结合每次跳完所在的下标的数组值，两者之和是局部最大值，作为判断的权重，决定局部最优，最后推导出的跳跃方案即是整体最优。

3.参考代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    if(nums.length==1){
        return 0;
    }
    var time=1;
    var target=nums.length-1;
    var journal=nums[0];
    var i=0;
    while (journal<target)
    {
        var weight=[];
        for(var j=1;j<=nums[i];j++){
            weight.push(nums[i+j]+j+i);
        }
        var max=0;
        var step=0;
        for(var j=0;j<nums[i];j++){
            if(weight[j]>max){
                max=weight[j];
                step=j+1;
              }
        }
        i+=step;
        time+=1;
        journal=max;
    }
    return time 
};

赏

感谢您的支持，加个好友吧

微信