【leetcode】45 Jump Game II

发表于 | 分类于 ，


描述

给定一个非负整数数组，您最初定位在数组的第一个索引处。数组中的每个元素表示该位置的最大跳转长度。您的目标是以最小跳跃次数到达最后一个索引。

样例

样例1

1
2
输入: [2,3,1,1,4]
输出: 2

样例2

1
2
输入: 1 4
输出: 1

思路

第一种方式，回溯，简单粗暴
第二种方式，贪心，跳到最远的地方去。我们不管怎么跳，总能到达最后一块石头。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
private:
    vector<int> dp;
public:
    int jump(vector<int>& nums) {
        for(int i=0;i<nums.size();i++){
            dp.push_back(-1);
        }
        int res = 0;
        return dfs(nums,0);
    }

    int dfs(vector<int> & nums,int index){
        if (dp[index] != -1){return dp[index];}
        if (index >= nums.size()-1 ){ return 0;}
        int min_val = 1<<30;
        for(int i= nums[index] ;i>0;i--){
            if(i + index < nums.size()){
                min_val = std::min(dfs(nums,index+i)+1,min_val);
            }
        }
        return dp[index] = min_val;
    }
};

优解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int jump(vector<int>& nums) {
        int reach=0, maxReach=0, res=0;
        for(int i=0; i<nums.size(); ++i) {
            if(reach<i) {
                reach=maxReach;
                ++res;
            }
            maxReach=max(maxReach, i+nums[i]);
        }
        return res;
    }
};

参考

原题链接