LeetCode 45.跳跃游戏Ⅱ（贪心、数组、动态规划dp）_45. 跳跃游戏 ii 动态规划

45.跳跃游戏Ⅱ

思路：方法一：dp,时间复杂度0（10^7）。dp[i]表示到i这个位置的最小步数。

class Solution {
public:
    int jump(vector<int>& nums) {
        int lens=nums.size();
        int dp[10010];
        memset(dp,0x3f,sizeof dp);
        dp[0]=0;
        for(int i=0;i<lens;i++){
            for(int j=1;i+j<lens&&j<=nums[i];j++){
                dp[i+j]=min(dp[i+j],dp[i]+1);
            }
        }
        //for(int i=0;i<lens;i++)
           //cout<<dp[i]<<" ";
        return dp[lens-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

思路：方法二：贪心，我们在跳到最远边界border之前，测量下一次能跳的最远距离current_max_lens。当到达边界i==border时，说明不得不跳，我们就更新跳的次数cnt++，同时更新边界border = current_max_lens。有一个注意点就是i<lens-1，这是因为到达第i个点就不需要跳了，已经结束了

class Solution {
public:
    int jump(vector<int>& nums) {
        int lens=nums.size();
        int border=0;//边界，必须跳的最远位置
        int current_max_lens=0;//下一次能跳的最远位置
        int cnt=0;//跳的次数
        for(int i=0;i<lens-1;i++){
            current_max_lens=max(current_max_lens,nums[i]+i);//每次都计算出当前跳的最远位置
            if(i==border){//如果到达边界，说明必须得跳了。这也是为什么i<lens-1的原因，因为最后一个点不需要跳
                cnt++;//更新跳的次数
                border = current_max_lens;//更新跳的最远位置
            }
        }
        return cnt;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17