LeetCode 45. 跳跃游戏 II**

基本思路:

总的来说两种思路,但是个人觉得DP更好一些;

DP思路:

直接建立一维DP思路,DP每个位置代表跳到该位置的最短距离;
时间复杂度为O(n^2)

贪心思路:

这个自己没想到,总是感觉贪心会爆时间;

个人感觉题解是脱了裤子放屁,既然找最远的,直接每次以最远距离为新的起点即可;

总体代码:

DP:

class Solution {
public:
    int jump(vector<int>& nums) {
        vector<int>dp(nums.size());
        dp[0]=0;
        for(int i=1;i<dp.size();i++){
            int min=INT_MAX;
            for(int j=0;j<i;j++){
                if(nums[j]+j>=i){
                    if(dp[j]+1<min){
                        min=dp[j]+1;
                    }
                }
            }
            dp[i]=min;
        }
        return dp[dp.size()-1];
    }
};

贪心思路:

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size()==1)
            return 0;
        int position=0;
        int stripe=0;
        while(1){
            int max=0;
            int next_p=0;
            for(int i=position+1;i<=position+nums[position];i++){
                if(i>=nums.size()-1){
                    return stripe+1;
                }
                if(max<nums[i]+i){
                    max=nums[i]+i;
                    next_p=i;
                }
            }
            position=next_p;
            stripe++;
        }
        return stripe;
    }
};
上一篇:LeetCode-30-串联所有单词的子串


下一篇:Leetcode 652. 寻找重复的子树 find-duplicate-subtrees