跳跃游戏-ii

[编程题]跳跃游戏-ii

热度指数：12482 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出一个非负整数数组，你最初在数组第一个元素的位置

数组中的元素代表你在这个位置可以跳跃的最大长度

你的目标是用最少的跳跃次数来到达数组的最后一个元素的位置

例如

给出数组 A =[2,3,1,1,4]

最少需要两次才能跳跃到数组最后一个元素的位置。（从数组下标为0的位置跳长度1到达下标1的位置，然后跳长度3到数组最后一个元素的位置）

示例1

输入

[2,3,1,1,4]

输出

算法知识视频讲解

华科不平凡

发表于 2020-08-10 15:00:22

符合动态规划的条件：每个状态与前一个状态有关——设到i的最少步数为f(i)，则f(i) = f(i的上一个点) + 1 初始状态是已知的——刚开始几个点的f与第一个点有关然后就是实现问题了，两个循环，外循环是遍历每个点，内循环是遍历当前点的“势力范围”。 class Solution { p 展开全文