HDU 1284 錢币兌換問題（完全背包）

Link：http://acm.hdu.edu.cn/showproblem.php?pid=1284

題意：給定1 2 3 與 n，問有多少種組成n的方法。

用dp[i][j]表示前i種前兌換成j的方案數

則 dp[i][j]=sum(dp[i−1][j])+sum(dp[i][j−a[i])

即i一個都不選和i至少選一個

用滾動數組進行優化 dp[j]=dp[j]+sum(dp[j−i])

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
const int N = ;
typedef long long ll;
ll dp[N];   //前i種錢兌換成j的方法 dp[i][j] -> dp[j]
int main(){
    int n;
    while(~scanf("%d", &n)){
        memset(dp, , sizeof(dp));
        dp[] = ;
        for(int i = ; i <= ; i++){
            for(int j = i; j < N; j++){
                dp[j] += dp[j - i];
            }
        }
        printf("%lld\n", dp[n]);
    }
}