动态规划--找零钱

 1 coins=[1,2,5,10,50,100] #硬币面值
 2 
 3 def cal_change(total):
 4     if total<=0:
 5         return 0
 6     else:
 7         res=[]
 8         for coin in [x for x in coins if x<=total]:
 9             num=1+cal_change(total-coin)
10             res.append(num)
11         return min(res)
12     
13 if __name__=='__main__':
14     for i in range(20,31):
15         print('{0}:{1} coins at least.'.format(i,cal_change(i)))

结果：

20:2 coins at least.
21:3 coins at least.
22:3 coins at least.
23:4 coins at least.
24:4 coins at least.
25:3 coins at least.
26:4 coins at least.
27:4 coins at least.
28:5 coins at least.
29:5 coins at least.
30:3 coins at least.

效率测试：

1 if __name__=='__main__':
2     import time
3     start=time.time()
4     print(cal_change(33))    
5     end=time.time()
6     print('time collapsed:{0} seconds'.format(end-start))

输出：

5
time collapsed: 27.66892910003662 seconds

高效改进版：使用字典记住已经算出来的结果。

import time
coins=[1,2,5,10,50,100] #硬币面值

cache=dict() #字典缓存，记住运算结果
def cal_change(total):
    if total in cache.keys():
        return cache[total]
    if total<=0:
        return 0
    else:
        res=[]
        for coin in [x for x in coins if x>=total:
            if total>=coin:
                num=1+cal_change(total-coin)
                res.append(num)
        cache[total]=min(res)
        return cache[total]

if __name__=='__main__':
    start=time.time()
    print(cal_change(33))    
    end=time.time()
    print('time collapsed:{0} seconds'.format(end-start))

输出：

5
time collapsed: 0.00035190582275390625 seconds

参考：https://www.cnblogs.com/jiayongji/p/7118895.html