动态规划算法
2021-05-01 07:30
阅读：651
凑成0元需要0个硬币 //d(0)=0
凑成1元需要1个1元硬币 //d(1)=d(0)+1
凑成2元需要2个1元硬币 //d(2)=d(1)+1
凑成3元需要3个1元硬币或者1个3元硬币，那么我们选择1个3元硬币 //d(3)=min{d(2)+1,d(3-3)+1}
凑成4元需要1个3元硬币，1个1元硬币 //d(4)=d(3)+1;
凑成5元需要1个3元硬币，2个1元硬币或者1个5元硬币，那么我们选择1个5元硬币 //d(5)=min{d(4)+1,d(5-5)+1}，为d(4)+1 = 1个3元硬币，2个一元的硬币，d（2）+1，也就是一个3元硬币，2个一元硬币，d（0）+1一个一元硬币
。。。。
抽离出来d(i)=min{ d(i-1)+1,d(i-vj)+1 }，其中i-vj >=0，vj表示第j个硬币的面值;因为只有1张面值vj的加上剩余的d（i-vj）就可以算出所有有可能的解，做一个
首先要抽离出最优子结构，其中d(i-1)+1，d（i-vj）+1
上一篇：Thread-线程的同步
下一篇：Spring 概述
评论
亲，登录后才可以留言！