硬币組合問題-非遞歸實作

給定不同面額的硬币和一個總金額，計算出組成該總金額的所需硬币的最小個數。

好久沒有刷算法題了，最近被問到這麼個問題，有點懵逼，連個動态規劃的狀态轉移方程都寫不出來了。實在是慚愧。決定沒事的時候，刷一些動态規劃的東西。

網上有很多教程，直接寫下狀态轉移方程：

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;
}