美文网首页动态规划
leetCode 45 jump-game-ii本来以为是道dp

leetCode 45 jump-game-ii本来以为是道dp

作者: pokorz | 来源:发表于2019-08-09 08:38 被阅读0次

给定一个数组,值是跳动区间,问跳多少次能跳完。

其实很简单,每个位置上对应一个能跳的区间的一个范围,取最远的就行,因为必须从第一个开始跳,所以局部最优即是全局最优。无需用到dp

简单代码实现如下

// 记录跳动的截止节点
int end = 0;
// 记录能跳区间里的最远值
int max = 0;
// 遍历节点, 最后一个
for (int i=0;i<nums.length-1;i++) {
    // 寻找能跳最远值
    if (nums[i] + i > max) {
        max = nums[i] + i;
    }
    // 走到上一个end节点, 需要更新步数然后,更新下一个end
    if (i == end) {
        cnt ++;
        end = max;
    }
}

相关文章

网友评论

    本文标题:leetCode 45 jump-game-ii本来以为是道dp

    本文链接:https://www.haomeiwen.com/subject/mdzqjctx.html