找錢問題 不知道能不能在這邊問～ - 推理遊戲

實際程式化的話是這樣，以{25, 20, 10, 5, 1}來說：

// 隔這個define去取data[a]的值只不過預防取到a < 0，其中MAX_INT是個很大的值
// ，使得如果取到a < 0時給出很大的值，就會直接被min捨棄掉
#define DATA(a) ((a >= 0) ? (data[a]) : (MAX_INT))

// 價值0時用的硬幣數為0
data[0] = 0;
// 從價值1開始跑到MAX_NUM
for(i = 1; i < MAX_NUM; i++)
{
// 某價值所需最少硬幣，就是扣掉各個幣值後的各個價值中，選用幣數最少的那個
// 加上1
data[i] = 1 + min(DATA(i - 25), DATA(i - 20), DATA(i - 10), DATA(i - 5),
DATA(i - 1));
}

主程式這樣就搞定了，跑完data[x]就是代表x這個價值需要多少硬幣。

令m為錢幣種類數、n為要算的最大價值的話，這程式時間複雜度是O(mn)，會遠
比用多層迴圈硬幹的O(n^m)好上太多。

--
「去質疑親眼所見的事是最愚昧的行為。這又分為兩種－－質疑自己所見是不是
真的，或是用見到的事去質疑沒見到的事。呵。」

－－芙莉雅，謊言事務所實現使者

--