贪心算法解题框架

一句话总结

回溯算法的剪枝优化是提前排除不可能的答案，使树结构尽可能小，最终的算法复杂度一般是指数级别；动态规划的备忘录优化是为了避免重复计算，把树形结构优化成线性结构，最终的算法复杂度一般是多项式级别。

上述两种优化只是减少了无效枚举，但依然都枚举了所有可行解，从而试图寻找最优的那个解。

贪心算法和它们的区别是：有些问题其实不需要完整地枚举所有可行解，就可以推导出最优解。这样一来，进一步减少了枚举空间，效率自然会更高。

---

举个简单的例子，就能直观地展现贪心算法了。

问题一

比方说现在有两种钞票，面额分别为 1 元和 100 元，每种钞票的数量无限，但现在你只能选择 10 张，请问你应该如何选择，才能使得总金额最大？

那你肯定会说，肯定是 10 张全拿 100 元的钞票，共计 1000 元，这就是最优策略。

但按照算法思维，这个问题的本质是做 10 次选择，每次选择有两种可能，分别是 1 元和 100 元，一共有 $2^{10}$ 种可能的选择。

所以你心里首先应该出现一棵高度为 10 的二叉树来枚举所有可行解，遍历这些可行解，然后可以得到最优解。

心里只要有这样一棵二叉树，就应该能写出代码：

// 定义：做 n 次选择，返回可以获得的最大金额
int findMax(int n) {
    if (n == 0) return 0;

    // 这次选择 1 元，然后递归求解剩下的 n - 1 次选择的最大值
    int result1 = 1 + findMax(n - 1);
    // 这次选择 100 元，然后递归求解剩下的 n - 1 次选择的最大值
    int result2 = 100 + findMax(n - 1);

    // 返回两种选择中的最大值
    return max(result1, result2);
}

这个算法的复杂度是二叉树的节点数量，是指数级别，非常高。不过到这里你应该已经看出来了，findMax(n - 1) 的值肯定都一样，那么 100 + findMax(n - 1) 必然大于 1 + findMax(n - 1)，因此可以进行优化：

// 优化一、没必要对两种选择进行比较了
int findMax(int n) {
    if (n == 0) return 0;
    int result = 100 + findMax(n - 1);
    return result;
}

// 优化二、递归改为迭代
int findMax(int n) {
    int result = 0;
    for (int i = 0; i < n; i++) {
        result += 100;
    }
    return result;
}

// 优化三、直接计算结果就行了
int findMax(int n) {
    return 100 * n;
}

这就是贪心算法，复杂度从 $O(2^n)$ 优化到了 $O(1)$，堪称离谱。

其实算法本来就很简单，就是枚举，是不是很简单？ 围绕枚举，衍生出各种优化方法，起了些名字，其实从原理上讲，没多大差别，不过是见招拆招罢了。

---

贪心选择性质

首先来举例说明什么是贪心选择性质。

开头举例的这个最大金额的问题符合贪心选择性质，所以我们可以用贪心算法，把 $O(2^n)$ 的暴力枚举算法直接优化到了 $O(1)$。

问题二

作为对比，我们稍微改一改问题一：

现在有两种钞票，面额分别为 1 元和 100 元，每种钞票的数量无限。现在给你一个目标金额 amount，请问你最少需要多少张钞票才能凑出这个金额？

这道题其实就是动态规划中讲解的凑零钱问题。

我们是如何解决问题二的？首先也是抽象出递归树，写出指数级别的暴力枚举算法，然后发现了重叠子问题，于是用备忘录消除重叠子问题，这就是标准的动态规划算法的求解过程，不能再优化了。

所以，问题二和问题一到底有什么区别？区别在于，问题二没有贪心选择性质，而问题一有。

贪心选择性质

贪心选择性质就是说能够通过局部最优解直接推导出全局最优解。

结合案例来说，对于问题一，局部最优解就是每次都选择 100 元，因为 100 > 1；对于问题二，局部最优解也是每次都选择 100 元，因为每张面额尽可能大，所需的钞票数量就能尽可能少。

但区别在于，问题一中每一次选择的局部最优解组合起来就是全局最优解，而问题二中不是。

比方说目标金额 amount = 3，虽然每次选择 100 元是局部最优解，但想凑出 3 元，只能选择 3 张 1 元，局部最优解不一定能构成全局最优解。

对于问题二的场景，不符合贪心选择性质，所以不能用贪心算法，只能枚举所有可行解，才能计算出最优解。

贪心选择性质 vs 最优子结构

动态规划中提到，算法问题必须要有「最优子结构」性质，才能通过子问题的最优解推导出全局最优解，这是动态规划算法的基础。

那么这个「贪心选择性质」和「最优子结构」有什么区别？

• 最优子结构的意思是说，现在我已经把所有子问题的最优解都求出来了，然后我可以基于这些子问题的最优解推导出原问题的最优解。
• 贪心选择性质的意思是说，我只需要进行一些局部最优的选择策略，就能直接知道哪个子问题的解是最优的了，且这个局部最优解可以推导出原问题的最优解。此时此刻我就能知道，不需要等到所有子问题的解算出来才知道。

所以贪心算法的效率一般都比较高，因为它不需要遍历完整的解空间。

---

例题实战

例题一：「跳跃游戏」

给你一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标，如果可以，返回 true；否则，返回 false。

示例 1：

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

示例 2：

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

注意题目说 nums[i] 表示可以跳跃的最大长度，不是固定长度。假设 nums[i] = 3，意味着你可以在索引 i 往前跳 1 步、2 步或 3 步。

我们先思考暴力枚举解法，如何枚举所有可能的跳跃路径？假设 N 为 nums 的长度，这道题相当于做 N 次选择，每次选择有 nums[i] 种选项，想要枚举所有的跳跃路径，就是一棵高度为 N 的多叉树，每个节点有 nums[i] 个子节点。

这个算法本质上还是枚举了所有可能的选择，可以走动态规划那一套流程进行优化，但是这里我们先不急，可以再仔细想想，这个问题有没有贪心选择性质？

题目的关键点：

1. 在索引 i，可以跳跃 1 ~ nums[i] 步。
2. 只要能跳到最后一个索引，就返回 true。

这里面有个细节，比方说你现在站在 nums[i] = 3 的位置，你可以跳到 i+1, i+2, i+3 三个位置，此时你真的需要分别跳过去，然后递归求解子问题 dp(i+1), dp(i+2), dp(i+3)，最后通过子问题的答案来决定 dp(i) 的结果吗？

其实不用的，i+1, i+2, i+3 三个候选项，它们谁能走得最远，你就选谁，准没错。

具体来说，i+1 能走到的最远距离是 i+1+nums[i+1]，i+2 能走到的最远距离是 i+2+nums[i+2]，i+3 能走到的最远距离是 i+3+nums[i+3]，你看看谁最大，就选谁。

这就是贪心选择性质，通过局部最优解就能推导全局最优解，不需要等到递归计算出所有子问题的答案才能做选择。

所以这道题的最优解法如下：

bool canJump(vector<int>& nums) {
    int n = nums.size();
    int farthest = 0;
    for (int i = 0; i < n - 1; i++) {
        // 不断计算能跳到的最远距离
        farthest = max(farthest, i + nums[i]);
        // 可能碰到了 0，卡住跳不动了
        if (farthest <= i) {
            return false;
        }
    }
    return farthest >= n - 1;
}

只需要遍历所有元素，记录当前能到达的最远位置就行了，时间复杂度是 $O(N)$，空间复杂度是 $O(1)$，非常高效。

---

例题二：「跳跃游戏 II」

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例：

输入: 2 3 0 1 4
输出: 2

现在的问题是，保证你一定可以跳到最后一格，请问你最少要跳多少次，才能跳过去。

暴力枚举肯定也是可以做的，我们可以定义这样一个 dp 函数：

// 定义：从索引 p 跳到最后一格，至少需要 dp(nums, p) 步
int dp(vector<int>& nums, int p);

题目问的就是 dp(nums, 0) 的结果，base case 就是当 p 超过最后一格时，不需要跳跃：

if (p >= nums.size() - 1) {
    return 0;
}

根据动态规划详解的动规框架，就可以暴力枚举所有可能的跳法，通过备忘录 memo 消除重叠子问题，取其中的最小值作为最终答案：

// 备忘录，全局变量或传递引用
vector<int> memo;

int dp(vector<int>& nums, int p) {
    int n = nums.size();
    // base case
    if (p >= n - 1) {
        return 0;
    }
    // 子问题已经计算过
    if (memo[p] != n) {
        return memo[p];
    }
    int steps = nums[p];
    // 你可以选择跳 1 步，2 步...
    for (int i = 1; i <= steps; i++) {
        // 枚举每一个选择
        // 计算每一个子问题的结果
        int subProblem = dp(nums, p + i);
        // 取其中最小的作为最终结果
        memo[p] = min(memo[p], subProblem + 1);
    }
    return memo[p];
}

int jump(vector<int>& nums) {
    int n = nums.size();
    // 备忘录都初始化为 n，相当于 INT_MAX
    // 因为从 0 跳到 n - 1 最多 n - 1 步
    memo = vector<int>(n, n);
    return dp(nums, 0);
}

这个解法已经通过备忘录消除了冗余计算，时间复杂度是递归深度 x 每次递归需要的时间复杂度，即 $O(N^2)$，在 LeetCode 上是无法通过所有用例的，会超时。

所以进一步的优化就只能是贪心算法了，我们要仔细思考是否存在贪心选择性质，是否能够通过局部最优解推导全局最优解，避免全量枚举所有的可能解。

和上面的题目是一样的优化思路：我们真的需要递归地计算出每一个子问题的结果，然后求最值吗？其实不需要。

站在索引 0 的位置，可以向前跳 1、2 或 3 步，应该选择跳多少呢？应该跳 2 步跳到索引 2，因为 nums[2] 的可跳跃区域涵盖了索引区间 [3..6]，比其他的都大。题目求最少的跳跃次数，那么往索引 2 跳必然是最优的选择。

这就是贪心选择性质，我们不需要真的递归枚举出所有选择的具体结果来比较求最值，而只需要每次选择那个最有潜力的局部最优解，最终就能得到全局最优解。

绕过这个弯儿来就可以写代码了。代码可能有点不好理解，关键在于对 i, end, farthest, jumps 几个变量的更新：

每次跳跃可达的是一个索引区间，代码中 [i, end] 维护当前的跳跃次数 jumps 可以覆盖的索引区间，farthest 表示从 [i, end] 区间内起跳，可以跳到的最远索引。

int jump(vector<int>& nums) {
    if (nums.size() <= 1) {
        return 0;
    }
    int n = nums.size();
    // jumps 步可以跳到索引区间 [i, end]
    int end = 0, jumps = 0;
    // 在 [i, end] 区间内，最远可以跳到的索引是 farthest
    int farthest = 0;
    for (int i = 0; i < n - 1; i++) {
        // 计算从索引 i 可以跳到的最远索引
        farthest = max(nums[i] + i, farthest);
        if (i == end) {
            // [i, end] 区间是 jumps 步可达的索引范围
            // 现在已经遍历完 [i, end]，所以需要再跳一步
            jumps++;
            end = farthest;
            if (farthest >= n - 1) {
                // 如果已经可以到达终点，则可以直接返回
                return jumps;
            }
        }
    }
    // 如果无法到达终点，则返回 -1
    return -1;
}

这个解法的时间复杂度是 $O(N)$，空间复杂度是 $O(1)$，可以通过所有测试用例。

---

贪心算法的解题步骤

贪心算法的关键在于问题是否具备贪心选择性质，所以只能具体问题具体分析，没办法抽象出一套固定的算法模板或者思维模式，判断一道题是否是贪心算法。

但注意：没必要刻意地识别一道题是否具备贪心选择性质。 你只需时刻记住，算法的本质是枚举所有，遇到任何题目都可以先想暴力枚举思路，枚举的过程中如果存在冗余计算，就用备忘录优化掉。

如果时间复杂度过高（从做题的角度看 提交结果超时），那就说明不需要枚举所有的解空间就能求出最优解，这种情况下基本上就需要用到贪心算法。你可以仔细观察题目，是否可以提前排除掉一些不合理的选择，是否可以直接通过局部最优解推导全局最优解。

*学习笔记

暂没有学习笔记，快来抢first blood ！