[白俊]2293号硬貨1


[白俊]2293号硬貨1


質問リンク:https://www.acmicpc.net/problem/2293

問題とI/O



質問へのアクセス


これはdp問題です.この問題は考えてみると単純だ.創造すべき価値(円)はdp配列に格納されて使用される.まずゼロ元のコインがあると仮定して、ゼロから始めます.したがってdp[0]=1であり、各硬貨を計算した.現在の価値は現在の価値から現在の硬貨の価値を差し引くことができる.
dp[i] = dp[i] + dp[i-coin[cur]]

コード実装(C++)

#include <iostream>
#include <cstring>

using namespace std;
int dp[10001];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    int n,k;
    cin >> n >> k;
    int coin[n];
    for(int i = 0 ; i < n ; i++){
        cin >> coin[i];
    }
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for(int i = 0 ; i < n ; i++){
        for(int j = coin[i] ; j <= k ; j++){
            dp[j] = dp[j] + dp[j-coin[i]];
        }
    }
    cout << dp[k] << "\n";

}