刷题笔记（经典题目汇总）

作者: Lareina林暖暖 | 来源:发表于2019-04-06 15:27 被阅读0次

1.硬币找零问题（腾讯q币找零）

image.png

解法：贪心策略只考虑最少需要的硬币总数而不考虑具体的组合
对于 1,2,5,10 构成的硬币

image.png

num       method          answer    maxCount
1       =     1             1           1    (1)
2       =   1 + 2           2           3    (1+2)
3       =   1 + 2           2           3     
4       =    1+2+2          3           5    (3+2)
5       =    1+2+2          3           5  
6       =    1+2+2+5        4           10   (5+5)
7       =    1+2+2+5        4           10
8       =    1+2+2+5        4           10        
9       =    1+2+2+5        4           10             
10     =    1+2+2+5         4           10
12     =    1+2+2+5+10      5           20   (10+10)
13     =    1+2+2+5+10      5           20
14     =    1+2+2+5+10      5           20
15     =    1+2+2+5+10      5           20
16     =    1+2+2+5+10      5           20
17     =    1+2+2+5+10      5           20
18     =    1+2+2+5+10      5           20
19     =    1+2+2+5+10      5           20
20     =    1+2+2+5+10      5           20    
21     =    1+2+2+5+10+10   6           30   (10+10+10)

详解：https://blog.csdn.net/rgnoh/article/details/78403872