给定一个长度为 n
的 0 索引整数数组 nums
。初始位置为 nums[0]
。
每个元素 nums[i]
表示从索引 i
向前跳转的最大长度。换句话说,如果你在 nums[i]
处,你可以跳转到任意 nums[i + j]
处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1]
的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]
。
示例 :
输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是2。从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
思路
思考一个问题:如果在位置j不能跳到位置i(j<i),那么j能跳到i+1吗?
注意,在j处能跳到的最远位置是下标j+nums[j]的位置。如果j不能跳到i,那么i就大于这个最远位置。
那么显然j是不能跳到i+1的的。记住这件事,他是求DP时贪心的关键条件。
解题过程
DP数组的实现就不必多说了,无非是dp[i]=dp[j]+1(到i的最少步数是j的步数+1,其中j是前面的所有能跳到i的位置里步数最少的)只是还不知道j是多少而已。
问题来了,对于每一个i,怎么找到前置j?
DP数组一定越来越大,所有我们一定要尽量从前开始找j。
为了跳到i,我们需要找到从前向后第一个j+nums[j]>=i的j。
但是对于每一个i,我们需要每次都从0开始找j吗?
回想到我们的思考:如果j不能跳到i,那自然就不能跳到i+1。
因此,j不需要重置为0:
i+1的前置j一定大于等于i的前置j。
主体部分如下:
for(int i=1,j=0;i<len;i++){
while(j+nums[j]<i)j++;
dp[i]=dp[j]+1;
}
复杂度
时间复杂度: O(n)
空间复杂度: O(n)
复杂度分析:
i会遍历一次数组,他的前置位置j也只会遍历一次数组,时间复杂度是线性级别的。
使用了常量空间的双指针和长度为n的DP数组,空间复杂度是线性级别的。
Code
class Solution {
public:int jump(vector<int>& nums) {const int len=nums.size();vector<int>dp(len,0);for(int i=1,j=0;i<len;i++){while(j+nums[j]<i)j++;dp[i]=dp[j]+1;}return dp[len-1];}
};