LeetCode刷题笔记-动态规划-day4

55. 跳跃游戏

1.题目

原题链接： 55. 跳跃游戏

2.解题思路

算法：贪心

我们用变量 j 表示从前 i-1 个位置跳能跳到的最远位置，遍历数组：

1. 如果当前位置 i 大于了 j ，表示我们从前 i-1 个位置中跳不到这里，因此也不能跳到最后一个位置，直接返回 false
2. 如果可以跳到 i ，则更新前 i 个位置可达到的最远距离 j 的值： j=max(j,i+nums[i]);

最后如果 j 达到了最后一个数就说明成功了，返回 true

3.代码

class Solution {
public:
    bool canJump(vector<int>& nums) {
        for(int i=0,j=0;i<nums.size();i++){
            if(j<i) return false;
            j=max(j,i+nums[i]);
        }
        return true;
    }
};

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10

45. 跳跃游戏 II

1.题目

原题链接： 45. 跳跃游戏 II

2.解题思路

算法：动态规划+贪心

我们用 f[i] 表示从起点跳到 i 点所需的最小步数。初始化 f[0]=0

我们发现 f[i] 是具有单调性的，也就是 f[i + 1] >= f[i] 。因为我们如果可以跳到 f[i+1] 是一定可以跳到 f[i] 的。

如果我们使用两遍循环动态规划的话，在更新每个点的最小值的时候是需要遍历所有能跳到 i 的点的，而 f[i] 有了单调性后，我们只需要用第一个能跳到 i 的点更新就可以，这样最后的步数一定是最小的。

3.代码

class Solution {
public:
    int jump(vector<int>& a) {
        int n=a.size();
        vector<int> f(n);
        for(int i=1,j=0;i<n;i++){
            while(j+a[j]<i) j++;
            f[i]=f[j]+1;
        }
        return f[n-1];
    }
};

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12