UVA.674 Coin Change (DP)

题意分析

有5种硬币， 面值分别为1、5、10、25、50，现在给出金额，问可以用多少种方式组成该面值。

每种硬币的数量是无限的。典型完全背包。

状态转移方程

dp[j+c[i]] = dp[j] + dp[j+c[i]]

代码总览

/*

    Title:UVA.674

    Author:pengwill

    Date:2017-2-16

*/

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define nmax 7505

using namespace std;

int dp[nmax];

int c[5] = {1,5,10,25,50};

int main()

{

    dp[0]=1;

    for(int i = 0;i<5;++i){

       for(int j = 0;j<=nmax;++j)

            dp[j+c[i]] = dp[j] + dp[j+c[i]];

    }

    int n;

    while(scanf("%d",&n) != EOF){

        printf("%d\n",dp[n]);

    }

    return 0;