leetcode 45

贪心算法

贪心算法是一种基于贪心策略的算法思想，它在每一步选择中都采取当前状态下最优的选择，从而希望能够得到全局最优解。

贪心算法的基本思想是通过局部最优解的选择来达到全局最优解。具体来说，贪心算法通常包含以下步骤：

1. 定义问题的优化目标，明确问题的限制条件。
2. 将问题分解为一系列子问题，每个子问题都可以通过贪心策略来求解。
3. 根据贪心策略，选择当前状态下最优的解决方案。
4. 更新问题的状态，继续迭代或者直到得到最终解。

贪心算法的优点是简单、高效，适用于一些特定类型的问题。然而，贪心算法并不保证能够得到全局最优解，因为它只关注当前步骤的最优解，而没有考虑未来可能的影响。因此，在使用贪心算法时，需要仔细分析问题的性质，确保贪心策略的正确性。

一些经典的贪心算法问题包括：找零钱问题、活动选择问题、背包问题、最小生成树问题等。

总之，贪心算法是一种简单而高效的算法思想，可以用于解决一些特定类型的问题，但需要注意贪心策略的正确性和问题的性质。

证明贪心的正确性

要证明贪心算法的正确性，需要证明两个方面：贪心选择性和最优子结构。

1. 贪心选择性：贪心选择性是指每一步都选择当前最优的解决方案，即在每一步中选择能够跳跃的最远位置。对于跳跃游戏2问题，我们每次选择能够跳跃的最远位置，即更新maxPosition的值。这样可以保证在遍历过程中，每次跳跃都是当前最优的选择。

2. 最优子结构：最优子结构是指问题的最优解可以通过子问题的最优解来构造。对于跳跃游戏2问题，我们可以将问题拆分成子问题，即从起点跳到每个位置的最小跳跃次数。假设我们已经知道了从起点跳到位置i的最小跳跃次数，那么从起点跳到位置i+1的最小跳跃次数可以通过以下方式计算：首先判断位置i是否超过了当前能够跳跃的边界位置end，如果超过了，说明需要进行一次跳跃，将步数加1，并更新边界位置为maxPosition。然后更新maxPosition为位置i+1和当前位置能够跳跃的最远位置之间的较大值。这样就可以得到从起点跳到位置i+1的最小跳跃次数。因此，问题的最优解可以通过子问题的最优解来构造，满足最优子结构的条件。

由于贪心选择性和最优子结构都成立，因此可以得出结论：贪心算法可以得到跳跃游戏2问题的最优解。

贪心答案

class Solution {
public:
    int jump(vector<int>& nums) {

        int maxP =0;
        int n =nums.size();
        int end =0;
        int step =0;

        for(int i=0; i< n-1; ++i){
            if(maxP >= i){
                maxP = max(maxP, i+nums[i]);
                if(i == end){
                    end = maxP;
                    step++;
                }
            }
        }
        return step;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

dp答案

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] f = new int[n]; 
        for (int i = 1, j = 0; i < n; i++) {
            while (j + nums[j] < i) j++;
            f[i] = f[j] + 1;
        }
        return f[n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11

没怎么仔细看这个dp， 粘贴个答案。

作者：宫水三叶
链接：https://leetcode.cn/problems/jump-game-ii/solutions/594093/xiang-jie-dp-tan-xin-shuang-zhi-zhen-jie-roh4/