[伯俊]BOJ 2293硬貨1 JAVA

8898 ワード
アルゴリズム#アルゴリズム# テキストリンク
BOJ 2293硬貨1

質問する


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

入力


最初の行はn,kを与える.(1≦n≦100,1≦k≦10000)次のn行は、各硬貨に価値を与える.硬貨の価値は100000以下の自然数である.

しゅつりょく


1行目の出力状況の数.ケースの数は2^31未満です.

サンプルI/O



ソースコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static int n, k;
    private static int[] coins, dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        coins = new int[n];
        dp = new int[k + 1];
        dp[0] = 1;

        for (int i = 0; i < n; i++) {
            coins[i] = Integer.parseInt(br.readLine());

            for (int j = coins[i]; j <= k; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }

        System.out.println(dp[k]);
    }
}

Comment


  • solved.acが提供する年齢測定は1銀難易度である.しかしdpを満たす点火式は設計されていない.
  • dp[A] = B
  • A:金額
  • B:A円の可能数
  • 例えば!
  • 2作成時の数
  • 1を使用して2を作成した場合、合計は1+1です.
  • 2を使用して2を作成する場合、合計は2で、1種類あります.
  • 3作成時の数
  • 1を使用して3を作成した場合、合計は1+1+1になります.
  • 2を使用して3を作成した場合、合計は1+2の1種類です.
  • 4作成時の数
  • 1を使用して4を作成した場合、合計は1+1+1になります.
  • 2を使用して4を作成する場合、1+1+2と2+2の2つのケースがあります.
  • 5作成時の数
  • 1を使用して5を作成した場合、合計は1+1+1+1になります.
  • 2を使用して5を作成する場合、1+1+2、1+2+2の2つのケースがあります.
  • 5を使用して作成された5の合計数は5で、1種類あります.
  • 結果は?
  • 2を使用して5を作成することを考慮すると、1と2を使用して3を作成した合計数です.
  • つまり、Aを使用してNを作成した数は、N-Aを作成した総数に等しい.
  • dp[j] = dp[j] + dp[j - coins[i]];
    • [非技術]作業記録_3
    [設計モード-🏗👷 作成]🏭 Factory Method Pattern