【完全背包】HDU-1284 錢币兌換問題

注解

1、完全背包。注意初始情況為dp[0]=1。

代碼

#include <iostream>
#include <cstring>

using namespace std;

const int MAX = 32768;
const int MAXTYPE = 3;
int coin[MAXTYPE] = {1, 2, 3};

int main() {

    int dp[MAX];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for(int i=0; i<MAXTYPE; i++) {
        for(int j=coin[i]; j<MAX; j++) {
            dp[j] += dp[j-coin[i]];
        }
    }

    int N;
    while(cin>>N) {
        cout<<dp[N]<<endl;
    }

    return 0;
}
           

結果