部分和問題を動的計画法で解く
部分和問題
code:prob.txt
n 個の正の整数 a0,a1,…,an−1 と正の整数 A が与えられる。これらの整数から何個かの整数を選んで総和が A になるようにすることが可能か判定せよ。可能ならば "YES" と出力し、不可能ならば "NO" と出力せよ。 制約
1 ≤ n ≤ 100
1 ≤ a[i] ≤ 1000
1 ≤ A ≤ 10000
解答
dp[i+1][j]
i番目までの整数の中からいくつか選んで総和を j とすることが可能かどうか
$ 0 \leq i \leq N + 1
$ 0 \leq j \leq A+1
Links