問題描述
100元換零錢1元、2元婚陪、5元、10元频祝、20元泌参、50元有多少種組合方案？
解題思路
使用動態(tài)規(guī)劃來求解常空，使用表示用不超過第
個面值（從小到大排序）的零錢來表示
的所有組合方案數(shù)沽一，則
程序?qū)崿F(xiàn)
int main()
{
int val[7] = { 0,1,2,5,10,20,50 };
int f[101][7];
memset(f, 0, sizeof(f));
for (int j = 0; j <= 6; j++)
f[0][j] = 1;
for (int j = 1; j <= 6; j++)
{
for (int i = 1; i <= 100; i++)
{
if (i - val[j] < 0)
f[i][j] = f[i][j - 1];
else
f[i][j] = f[i - val[j]][j] + f[i][j - 1];
}
}
cout << f[100][6] << endl;
system("pause");
return 0;
}
