uva 674 - Coin Change

题目意思：有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.zzzyk.com
int main(){
    //freopen("input.txt" , "r" , stdin);
    solve();
    while(scanf("%d" , &n) != EOF) printf("%d\n" , dp[n]);
    return 0;
}

作者：cgl1079743846

补充：软件开发 , C++ ,