贪心算法解题套路框架

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

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

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

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

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

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

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

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

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

比如下面这个可视化面板画出了这棵递归树，不过因为做 10 次选择产生的二叉树太大，这里只画了做 3 次选择的情况：

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

// 定义：做 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(1)$，堪称离谱。

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

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

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