给定不同面额的硬币和总额，计算出构成该总额所需的硬币的最小个数。 好久没刷算法问题了，最近被问到这样的问题，我有点无知，连动态规划的状态转移方程都写不出来了。 真的很不好意思。 决定没问题的时候，磨练一下动态计划的东西。
网上有很多教程。 请直接写下状态转移方程式：
f(n )=min(f(n-k )，kincoins ) 1。 在这里，coins是给定面额不同的硬币的集合。
递归的实现比较简单，根据状态方程直接写即可。 但是递归的情况下，堆栈是有限制的，计算的n比较有限。 所以最好换成循环来实现。
在此，使用广域搜索这样的方法，计算n的值。 (因为懒得写list了，所以直接使用c的queue。 的非优雅代码如下。
# include stdio.h # includequeueintcoins [ ]={ 1，7，11 }； #define MAX 10000int ret[MAX]={0}； #definemin(a，b ) (a ) ) b )？ (a ) 3360 ) b ) intgetn(intn，int size )//只计算小于max的if ) n=max ) return 0； //ret和初始化queue std:queueint q的for(intI=0； i size； I ) { ret[coins[i]]=1； q.push(coins[I] )； (} int f，t； while(q.size )0) )//queue的各元素进行遍历，与coins结合，将新结果放入queue的int f=q.front )； for(intI=0； i size； I () { t=f coins[i]； //新结果if(tMAXt=n )//新结果小于max，且目标结果n(if ) ret(t )==0初始配置金额t的硬币数量ret(t )=ret(f ) 1； 第else //次以后的构成金币t的硬币枚数必须小于以前储存的结果才能更换。 ret[t]=min(ret[t]，ret[f] 1)； q.push(t )； //新结果放在queue上后等待广泛搜索} } q.pop (； //移除已经匹配的路径} return ret[n]； ///返回期望值(}int main ) ) intsize=sizeof ) coins )/sizeof ) int )； intret=getn(14，size )； printf(%d(n )，ret )； 返回0； }