一个点从nums数组的初始位置出发,每处可前进的步数<=nums[i],问是否能到达nums的终点位置。记录目前可达的最右位置rightmost,若i<=rightmost,rightmost=max(rightmost,i+nums[i]),若rightmost>=n-1,即能到达最终位置或更远的位置,说明可达,否则,不可达。
在保证点能到达最终位置的情况下,点移动的最少次数。我使用动态规划方法做,时间复杂度O(n^2),空间复杂度O(n),运行的代码只打败了%5的人,官方题解给出的策略是贪心,维护每个节点到达的最远位置,最远边界end初始化为end,若end==i,则end=rightmost,step++
参考链接:55. 跳跃游戏
45. 跳跃游戏 II