題目意思： 有5種硬幣 1 ， 5 ， 10 ， 25 ， 50 ，現在給我們一個數n，求用這5種硬幣組成和為n的總方案數是多少
解題思路： 動態規劃
1:如果硬幣只由1分組成，那麼總方案數就是1
2:如果硬幣由1和5組成，那麼總方案數就是1+s1 (s1為1和5組成的方案)
.
.
.
6:如果硬幣由1，5，10，25，50組成，那麼總方案數就是1+s1+s2+s3+s4+s5
題目給出的數據n最大為7489，那麼我們采用的是先把所有的值的拆分的總方案數求出來（也就是打表），然後輸入一個我麼直接輸出即可。
思路：我們用type[5]數組存儲5種硬幣，設dp[i][j]表示用前i+1種（type[0]....type[i]）組成價值為j的總方案數，那麼我麼就可以直接兩重循環去枚舉每一個價值j，求出所有的數據，最後查找輸出。
代碼：
[cpp]
//（沒有優化）
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;
#define MAXN 8000
int type[5] = {1,5,10,25,50};
int dp[5][MAXN];//用int類型即可，如果MAXN上萬要用unsigned long long
int n , ans;
//打表處理好所有的數據
void solve(){
for(int i = 0 ; i < 5 ; i++){
for(int j = 0 ; j < MAXN ; j++){
if(i == 0 || j == 0) dp[i][j] = 1;//i為0說明只由1組成那麼dp[i][j]為1，j為0說明價值為0的組成方案只有1種（如果看成0則會WA）
else dp[i][j] = 0;//其它全部初始化為0
}
}
for(int i = 1 ; i < 5 ; i++){//i-1出現，那麼從1開始枚舉
for(int j = 1 ; j < MAXN ; j++){
for(int k = 0 ; k*type[i] <= j ; k++)//k個type[i]，注意必須從0開始
dp[i][j] += dp[i-1][j-k*type[i]];//加上前面的方案數
}
}
}
int main(){
//freopen("input.txt" , "r" , stdin);
solve();
while(scanf("%d" , &n) != EOF){
for(int i = 4 ; i >= 0 ; i--){
if(dp[i][n]) { ans = dp[i][n] ; break;}//從末尾開始查找只要有一個不為0就是答案
}
printf("%d\n" , ans);
}
return 0;
}
//（將二維優化成一維）優化後的代碼
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;
#define MAXN 8000
int type[5] = {1,5,10,25,50};
int dp[MAXN];//dp[i]表示價值i的總的方案數
int n , ans;
//打表處理好所有的數據
void solve(){
memset(dp , 0 , sizeof(dp)) ; dp[0] = 1;//注意dp[0] = 1這個條件
for(int i = 0 ; i < 5 ; i++){
for(int j = 1 ; j < MAXN ; j++){
if(j-type[i] >= 0) dp[j] += dp[j-type[i]];//累加起來
}
}
}
www.2cto.com
int main(){
//freopen("input.txt" , "r" , stdin);
solve();
while(scanf("%d" , &n) != EOF) printf("%d\n" , dp[n]);
return 0;
}
