2.4 贪心算法

2.4.1 什么是贪心算法

贪心算法的核心思想是在每一步中**都选择当前状态下的最优解，而不考虑全局后果。**它通常适用于那些问题，其最优解可以通过一系列局部最优解的组合得到。

贪心算法的一般步骤如下：

• 选择阶段： 从问题的所有可能选择中，选择一个局部最优解。

• 限制阶段： 将问题规模缩小，转化为一个子问题。

• 最优解合并阶段： 将局部最优解与子问题的解合并，得到全局最优解。

• 核心思想：贪心算法：从当前的数据可以推断以后的数据；动态规划，以前的数据可以推断现在的数据。 注意区分两者的思想，虽然思想不同，但是贪心算法可以解的题也可以用动态规划来解，只是动态规划的时间复杂度与空间复杂度都相对于贪心算法更高一些。

贪心算法的关键是选择合适的贪心策略，以确保每一步都是局部最优的。然而，需要注意的是，贪心算法并不总能得到全局最优解，因此在应用时需谨慎考虑问题的性质。这样描述可能有点抽象，下面通过几道例题进行加深你的理解。

2.4.2 贪心算法的适用场景

递归算法适用于：

问题可以被分解为更小的子问题进行求解的场景 局部最优即全局最优的场景，如何证明局部最优可得到全局最优这是贪心算法的难点。 一些常见的应用场景包括：

• 活动选择问题： 给定一系列活动，每个活动有开始时间和结束时间。目标是选择最大数量的不重叠活动，使得参与活动的人数最多。

• 霍夫曼编码： 在数据压缩中，霍夫曼编码是一种用于压缩数据的贪心算法。它通过为出现频率较高的字符分配较短的编码来减少数据的存储空间。

• 最小耗费生成树（Prim算法）： 在图中寻找最小生成树的问题中，Prim算法通过从一个初始节点开始，逐步选择与当前树相连的边中权值最小的边，从而构建最小生成树。

• 零钱兑换问题： 给定一些面额不同的硬币和一个目标金额，找出使用最少的硬币来达到目标金额。

• 分数背包问题： 在背包问题中，每个物品有一定的价值和重量，但可以分割成较小的部分。贪心策略是优先选择单位价值最高的物品。

2.4.3 贪心算法模板

2.4.4 贪心算法详解

2.4.4.1 leetcode 55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

分析：

• 我们可以从当前位置推断能跳到的最大位置， 即 max = Math.max(max, nums[i] + i)。
• 只要当前位置与能跳到的最大位置相等，即i == max，则表示后续的位置便到达不了了。

代码实现：

// 贪心算法解法
class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length == 1) return true;
        int max = 0; // max 表示当前可以跳到的最大距离
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] + i > max) max = nums[i] + i;
            if (i == max) return false;
        }
        return true;

    }
}