Uva 674Coin Change

題意：給一個數，用題目給的5個數任意相加使得等于那個數，輸出有多少種

完全背包問題，狀态轉移方程dp[i]=dp[i]+dp[i-a[j]];a[j]是5個數的一個。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
const int m = 10000;
int main()
{
    int dp[m];
    int sum;
    int h=0;
    int a[5]={50,25,10,5,1};
    while(~scanf("%d",&sum))
    {
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        for(int i=0;i<5;i++){
            for(int j=a[i];j<=sum;j++){
                dp[j]=dp[j]+dp[j-a[i]];
            }
        }
        cout << dp[sum] << endl;
    }
}