硬币组合问题-非递归实现

给定不同面额的硬币和一个总金额，计算出组成该总金额的所需硬币的最小个数。

好久没有刷算法题了，最近被问到这么个问题，有点懵逼，连个动态规划的状态转移方程都写不出来了。实在是惭愧。决定没事的时候，刷一些动态规划的东西。

网上有很多教程，直接写下状态转移方程：

F(N) = Min{ F(N-k), k in coins } + 1, 其中coins是给定不同面额的硬币的集合。

递归实现比较简单，直接根据状态方程写即可。但是递归的时候，栈是有限制的，计算出来的N比较有限。所以最好改成循环实现。

这里用了一种类似广搜的方法(在深入的研究中发现广搜这个方法实在是太笨了，效率很差，请不要学习，完全只需要一个记录表即可)，计算N的值。（懒得写list了，直接用c++的queue）。大致的非优雅代码如下：

#include <stdio.h>
#include <queue>

int coins[] = {1, 7, 11};

#define MAX 10000
int ret[MAX] = {0};

#define min(a, b)  (a) < (b) ? (a) : (b)

int getN(int n, int size)
{
	// 只计算小于MAX的
    if(n >= MAX)
        return 0;

	// 初始化ret和queue
    std::queue<int> q;
    for(int i = 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(int i = 0;i < size; i ++)
        {
            t = f + coins[i];    // 新的结果
            if(t < MAX && t <= 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()
{
    int size = sizeof(coins)/sizeof(int);
    int ret = getN(14, size);
    printf("%d\n", ret);

    return 0;
}