白駿2293硬貨1

質問する

2293硬貨1題リンク
n種類のコインがあります.コイン1枚あたりの価値は違います.このコインを適当に使って、価値の和をk元にしたいです.その場合の数を求める.コイン1枚につきいくつか使えます.
使用するコインの構成は同じですが、順番が違うのは同じ場合です.

に答える

問題で指定したサンプル入力を使用すると、

3 10
1
2
5

下図のように行います.(8-10スキップ)

コイン1時(青い蛍光ペン)、dp[1]からdp[10]に移動し、dp[i] += dp[i-1]を計算します.
コイン2は(ピンクの蛍光ペン)、dp[2]からdp[10]に移動し、dp[i] += dp[i-2]を計算します.
つまり、赤いペンで示す部分を例にとると、dp[6]に4を加えた場合はすべて「硬貨2」を1つ加えることができるので、dp[6]にdp[4]を加えた値になります.

ソースコード

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, k;
    cin >> n >> k;
    vector<int> vec(n);
    for (int i = 0; i < n; i++) {
        cin >> vec[i];
    }
    vector<int> dp(k + 1, 0);
    dp[0] = 1;

    for (int i = 0; i < n; i++) {
        for (int j = vec[i]; j <= k; j++) {
            dp[j] += dp[j - vec[i]];
        }
    }
    cout << dp[k];

    return 0;
}

DPはまだ難しい😂 最初は構成が同じであれば順序が違っていても同じ場合の条件だと考えず、解くために迷っていました.