题目链接

跳跃游戏 II

题目描述

注意点

• 题目保证可以到达 nums[n - 1]

解答思路

• 可以从后往前推出那些位置可以跳到目标点（最初是到终点），但是可能会有多个位置都能跳到目标点，此时可以贪心地取目标点最远的点作为新的目标点（一定保证步数最少），以此类推直到起点为止

代码

class Solution {public int jump(int[] nums) {int step = 0;int loc = nums.length - 1;while (loc > 0) {for (int i = 0; i < loc; i++) {if (i + nums[i] >= loc) {loc = i;step++;}}}return step;}
}

关键点

• 反向查找出发位置
• 贪心算法找到最小跳跃数