【算法：贪心】：贪心算法介绍+基础题（四个步骤）；柠檬水找零（交换论证法）

🎁个人主页：我们的五年

🔍系列专栏：C++课程学习

🎉欢迎大家点赞👍评论📝收藏⭐文章

前言：

暑假马上就要留校学习算法了，现在先学习一下基本的算法打打基础。本篇要讲的是贪心算法的介绍，然后会讲两道基础的题目，用的贪心证明方法是：交换论证法。目前对贪心算法还是很感兴趣的，贪心没有固定的解法，遇到不会的，希望我可以把这种贪心算法搞清楚。

贪心算法：

🍩1.概念：

贪心算法是把问题分成很多步，每次都是选择看起来最优的那一步，就可以得到正确的答案。能用贪心解决的问题是具有贪心性质的。要想能用贪心解题，需要充分挖掘题目的条件。而且没有固定的模式。

🍩2.步骤：

对于一道贪心题，要解决并学会，可以分为：

1.题目解析。2.算法原理。3.手撕代码。4.贪心策略证明。

对于一道贪心题，可能前三步很简单，但是第四步一定是可以多多思考，多多证明的。在证明贪心策略的过程也是很有趣的。

🍩3.对于学习贪心算法建议：

贪心算法，没有一个固定的模式，我不是孙膑。我更多是去学习别人的贪心方法，并理解运用。所以在遇到有一些贪心问题的时候，我们可能没有任何思路，但是我们可以看别人的贪心解法，然后学习别人的思路。能把别人想出来的东西运用，也是一节伟大事情。

例题1

LeetCode：柠檬水找零（860）

860. 柠檬水找零 - 力扣（LeetCode）

🍩1.题目解析：

●每杯柠檬水售价5元。

●顾客排队购买。

●顾客向你付给你的钞票面额：5元，10元，20元。对于10元的，要找一张五块钱。对于20元的，你可以找三张五块钱，也可以找一张五块钱和一张十块钱。

●一开始没有零钱，也就是只能有顾客的钱来找零。

🍩2.算法原理：

1.对于顾客给的五块钱，我们直接收下，不需要找零。

2.对于顾客付的十块钱，我们将十块钱收下，然后进行找五块钱。

3.对于顾客付的二十块钱，我们有两种找零的方式。

找零一：找三张五块钱的。

找零二：找一张十块钱的，找一张五块钱的。

🚁🚁🚁

从上面三种情况来看，五块钱有两种用途，十块钱只有一种用途（十块钱只能用来找零二十块钱的）。贪心解的情况下就是在找零二十块钱的时候，如果有十块钱就先用十块钱找（即找零方法一）。如果没有十块钱，才用三张五块钱进行找零。

🍩3.手斯代码：

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five=0,ten=0;   //20元有和没有都没关系
        for(auto& i:bills)
        {
            if(i==5)
                ++five;
            else if(i==10)
            {
                if(five)
                {
                    --five;
                    ++ten;
                }
                else
                    return false;
            }
            else if(i==20)
            {
                //有十块钱时，先用十块钱
                if(ten&&five)
                {
                    --ten;
                    --five;
                }
                else if(five>=3)
                {
                    five-=3;
                }
                else
                    return false;
            }
        }
        return true;
    }
};

🍩4.证明贪心策略：

在这道题中，贪心解和正确解的不同只发生在找零二十块钱的时候，贪心解用十块钱和五块钱进行找零，正确解用三张五块钱的进行找零。

🎡情况一：对于贪心解中用的十块钱，如果后面我们没有在正确解中用这十块钱，就直接用十块钱替换正确解的两种五块钱就得到了贪心解。

🎡情况二：如果后面正确解要用贪心解里的十块钱，那么此时用两张五块钱进行替换，也是满足最优性质的。