贪心算法思想草稿

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

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

那你肯定会说，这还用问么？肯定是 10 张全拿 100 元的钞票，共计 1000 元，这就是最优策略，但凡犹豫一秒就是傻瓜。

你这么说，也对，也不对。

说你对，因为这确实是最优解法，没毛病。

说你不对，是因为这个解法暴露的是你只想捞钱的本质 (¬‿¬) ，跳过了算法的产生、优化过程，不符合计算机思维。

那计算机就要提问了，
一切算法的本质是穷举，现在你还没有穷举出所有可能的解法，凭什么说这就是最优解呢？

按照算法思维，这个问题的本质是做 10 次选择，每次选择有两种可能，分别是 1 元和 100 元，一共有
2
10
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 Math.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(2
n
) 优化到了
O
(
1
)
O(1)，堪称离谱。

你可能会认为这个例子太简单？

其实算法本来就很简单，就是穷举，有什么了不起的嘛？围绕穷举，衍生出各种优化方法，起了些花里胡哨的名字，不懂的人就容易被名字骗到，其实从原理上讲，没多大差别，不过是见招拆招罢了。

上面的例子虽然简单，但已经蕴含了贪心算法的精髓。接下来我们拓展延伸一下，在真实的算法问题中，如何发现贪心选择性质，如何用贪心算法解决问题。

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

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

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

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

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

为了方便讲解，本文开头的最大金额问题我们称为「问题一」，这里的最少钞票数量问题我们称为「问题二」。

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

所以，问题二和问题一到底有什么区别？区别在于，前者没有贪心选择性质，而后者有。
（这个关于贪心选择性质的部分非常重要！请豆包着重讲解！划重点！！！多举例子 其他算法题的对比的例子！有贪心和无贪心的横向对比的例子！！！就像这里的最少钞票问题和最大金额问题！）
贪心选择性质

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

我们求解最少钞票问题时 首先是抽象出 递归树！写出指数级暴力穷举递归算法！然后发现了重叠计算！用备忘录消除重叠子问题！之后还可以改成dp数组

最大金额问题中 的贪心性质：每次选最大面值 组合起来所有选择就是全局最优！！

最少钞票数问题中不是这样！比方说目标金额 amount = 3，虽然每次选择 100 元是局部最优解，但想凑出 3 元，只能选择 3 张 1 元，局部最优解不一定能构成全局最优解。不符合贪心选择性质，所以不能用贪心算法，只能穷举所有可行解，才能计算出最优解。

所以贪心算法的本质也是一种剪枝！?(豆包深入解释下！对比暴力搜索这种遍历！？)

重点来了：

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

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

那么就有读者搞不清楚了，这个「贪心选择性质」和「最优子结构」有什么区别？

最优子结构的意思是说，现在我已经把所有子问题的最优解都求出来了，然后我可以基于这些子问题的最优解推导出原问题的最优解。

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

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

例题实战
先来看第一道例题，力扣第 55 题「跳跃游戏」：

55. 跳跃游戏 | 力扣 | LeetCode | 🟠
    给你一个非负整数数组 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 ， 所以永远不可能到达最后一个下标。
提示：

1 <= nums.length <= 104
0 <= nums[i] <= 105
题目来源：力扣 55. 跳跃游戏。

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]，你看看谁最大，就选谁。

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

class Solution {
public:bool canJump(vector<int>& nums) {int n = nums.size();int farthest = 0;for (int i = 0; i < n; i++) {// 不断计算能跳到最远的距离！farthest = max(farthest, i + nums[i]);if (farthest <= i) {return false;}}return farthest >= n-1;}
};

只需要不断遍历所有元素，并且计算出能到达的最远距离即可！如果遍历到某个位置i，发现达不到这里！只需要遍历所有元素，记录当前能到达的最远位置就行了，时间复杂度是
O
(
N
)
O(N)，空间复杂度是
O
(
1
)
O(1)，非常高效。

第二道例题，力扣第 45 题「跳跃游戏 II」：

45. 跳跃游戏 II | 力扣 | LeetCode | 🟠
    给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:

输入: nums = [2,3,0,1,4]
输出: 2
提示:

1 <= nums.length <= 104
0 <= nums[i] <= 1000
题目保证可以到达 nums[n-1]
题目来源：力扣 45. 跳跃游戏 II。
现在的问题是，保证你一定可以跳到最后一格，请问你最少要跳多少次，才能跳过去。

暴力穷举递归可以做出来！
定义dp§ 为 从索引p跳到最后一格n-1位置至少需要dp§步！

// 定义：从索引p跳到最后一格n-1位置, 至少需要dp(p)步
int dp(int nums[], int p);

base case 就是当p超过最后一格或到达最后一格的时候不需要跳！return 0

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

思路一：暴力穷举所有跳法 + 备忘录

class Solution {
public:vector<int> memo;// 主函数签名：jump(nums) 输出从0开始最少需要步数int jump(vector<int>& nums) {int n = nums.size();// 最后一格为n-1,设置备忘录长度n, 且最多不可能跳n步！所以初始化memo为nmemo = vector<int>(n, n);return dp(nums, 0);}// dp(nums, p)定义：从索引 p 跳到最后一格，至少需要 dp(nums, p) 步int dp(vector<int>& nums, int p) {int n = nums.size();// base caseif (p >= n - 1) {return 0;}// 如果子问题已经记录过if (memo[p] != n) {return memo[p];}// 如果第一次到p// 记录下p位置的可以跳的最大步数stepsint steps = nums[p];// 即有 1, 2, ... nums[p] 种选择！遍历所有选择for (int i = 1; i <= step; i++) {// 穷举每一个选择，计算每个子问题的结果int subProblem = dp(nums, p + i);// 取出其中最小的一次作为结果memo[p] = min(memo[p], subProblem + 1);}return memo[p];}
};

这个解法已经通过备忘录消除了冗余计算，但是还是会超时！
分析时间复杂度 = 递归深度 x 每次递归需要的时间复杂度

所以我们考虑进一步优化！
思考是否符合贪心选择的性质？
能否通过局部最优解推导出全局最优？？这样就能避免穷举所有可能解
真的需要递归计算每个子问题的结果么？

上图 当我们站在起始索引0 位置
可以向前跳动1， 2， 3步
其中分别对应新的nums值为1，4，2
我们可以很确定的说，直接选择跳2步即可！跳 2 步调到索引 2，因为 nums[2] 的可跳跃区域**涵盖了索引区间 [3…6]，**比其他的都大。题目求最少的跳跃次数，那么往索引 2 跳必然是最优的选择。

这就是贪心选择 我们不需要真的穷举递归所有选择的具体结果！只需要每次选择前！选择最具潜力的局部最优解！！最终必然可以得到全局最优！

每次跳跃可达的是一个索引区间！

• 代码中[i, end]维护当前的跳跃次数jumps可以覆盖的索引区间
• farthest表示从[i, end]起跳可以跳到的最远索引！！

维护四个量：

• 当前jumps次跳跃下
• 可达的索引区间[i, end]
• 从这个区间可以跳到最远的地方farthest！

class Solution {
public:int jump(vector<int>& nums) {// 边界情况if (nums.size() <= 1) {return 0;}// 本题维护的量int n = nums.size();// 当前 jumps 步可以跳到索引区间 [i, end]int jumps = 0；int end = 0;// 在区间 [i, end] 最远可以跳到farthestint farthest = 0;// 不断更新 end jumps 和 farthest// 当farthest已经到达n-1直接返回jumpsfor (int i = 0; i < n - 1; i++) {// 当前跳了jumps次, 到达了[i,end], 并且遍历前面的内容(<i)后最远跳到farthest// 遍历到i后, 先看看farthest是否更新！？farthest = max(farthest,i + nums[i]);// 这个是当前区间再走一步最远可以到的位置！！！所以如果这个farthest>=n-1那么要返回的是jumps+1！！！需要隐式的加上一步！if (farthest >= n-1) return jumps + 1;// [i,end]是jumps步可达的位置// 如果已经遍历完了[i,end]// 即i==endif (i == end) {// 更新end为farthest// 同时相当于多跳了一步jumps++;end = farthest;// 也可以在这里检查farthest到没到n-1,到了的话直接返回jumps！				}}// 遍历到n-2位置都没使得farthest>=n-1说明到不了终点！！return -1;}
};

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

至此，两道例题都解决了。

最后总结！
贪心算法关键在于问题是否

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

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

如果提交结果还是超时，那就说明不需要穷举所有的解空间就能求出最优解，这种情况下肯定需要用到贪心算法。你可以仔细观察题目，是否可以提前排除掉一些不合理的选择，是否可以直接通过局部最优解推导全局最优解。