一道找零钱的变种题

你是一个小贩，卖热狗。一个热狗5元。每个顾客只卖一个热狗，每次只收5，10，或20元面额纸币。给一串数字，表示每个来买热狗的顾客给的面额，返回true or false来表示可能不可能有足够零钱找给每个顾客。注意要按照客户的顺序，假设给的钱只会是5,10,或20，每次就买一个热狗。

比如 5,5,5 就是true。
5,5,20 false
5,5,5,5,20,10 false
5,5,5,10,10 true

第三个例子没看明白， 为什么5， 5， 5， 5， 20， 10 不行？ 4张5块够找15和5了，不知道是不是应该只有3个5。

如果说一定要按顺序写的话， 那就其实只需要考虑5和10的个数。5不需要找钱， 10 需要5， 20可以10也可以5。拿到的20都不能找出去，所以其实没什么用。
简单的想法的话，应该是挺greedy的，每次都用最大的面额去找钱，然后用一个array来记录剩下的钱。大概这样吧。。

1.     boolean hotdog(int[] purchase)
   
2.     {
   
3.         int[] changes = new int[2];
   
4.         for(int p : purchase)
   
5.         {
   
6.             if(p == 5) changes[0]++;
   
7.             if(p == 10)
   
8.             {
   
9.                 if( changes[0] < 1) return  false;
   
10.                 changes[0]--;
    
11.             }
    
12.             if(p == 20)
    
13.             {
    
14.                 if(changes[1] > 0)
    
15.                 {
    
16.                     changes[1]--;
    
17.                     if(changes[0] > 0) changes[0]--;
    
18.                     else return  false;
    
19.                 }
    
20.                 else
    
21.                 {
    
22.                     if(changes[0] > 3) changes[0] -= 3;
    
23.                     else return false;
    
24.                 }
    
25. 
    
26.             }
    
27.         }
    
28.         return true;
    
29.     }

复制代码

显然了， 接下来会问你如果这些零钱改了的话， 你的代码怎么修改？ 那其实还是可以用一个array 或者 list， 只不过大小不太确定。而且如果给的零钱比较奇特的话， 就不能用greedy了， 必须用dp
举个例子， 假如零钱可以是 1， 3， 4， 5 的话， 找7就会返回 5， 1， 1， 而不是 4， 3。。 注意这个就好。