【贪心算法】柠檬水找零

1.题目解析 [860 柠檬水找零 - 力扣（LeetCode）]( change/description/ “860. 柠檬水找零 - 力扣（LeetCode）”) 2.讲解算法原理 分情况讨论 5—》直接收下 10—》找五元，收下 20—-》10+5△ -—》5+5+5 由于5元更有用，则尽可能保留5元 3.代码 class Solution { public boolean lemonadeChange(int[] bills) { int five=0,ten=0; for(int x:bills){ if(x==5){ five++; }else if(x==10){ if(five==0){ return false; }else{ five–; ten++; } }else{ if(ten!=0&&five!=0){ ten–; five–; }else if(five>=3){ five-=3; }else{ return false; } } } return true; } } 4.证明 证明策略：交换论证法 贪心解：a,b,c,d,e,f 最优解：e,b,c,d,a,f 在不破坏最优解的“最优性质”的前提下，能够将最优解调整成贪心解