はじめに --- DP は役に立つ

はじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。
好きなアルゴリズムは最小カットやマッチングですが、会社ではなぜか「DP が好きな人」と呼ばれています。

巷ではよく「DP なんて実務では使わない」といった言説が定期的に流れますが、そんなことはないです。僕自身この 2 年間で DP が使える実務案件に 3 件くらい関わりました！

それはともかくとして、DP を学び立ての方がよく抱く悩みとして「バリエーションが多すぎて混乱するし、統一的なフレームワークがほしい」というのがあります。確かに DP のバリエーションは非常に多岐にわたるのですが、そのほとんどが以下の 3 つのフレームワークで説明できると思います:

• ナップサック DP
• 区間 DP
• bit DP

今回はとにかく「習うより慣れろ」の精神で、これらのパターンの例題を幾つか解くことで、自然に典型的な DP の世界を俯瞰することを目指します。今回はナップサック DP について書いて、次回以降に区間 DP, bit DP と続きます。なお、ナップサック DP だけを取り上げても、この記事には書ききれないようなテクニックが沢山あります。それらに触れられるような問題集をまた別途作りたいと考えています。

　
[注意]

• 動的計画法を始めて学ぶ方、本記事の内容が難しく感じる方向けの記事も書きました。先に読んでいただくと DP テーブル更新のイメージが掴みやすくなると思います。

  • 動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集

• ナップサック DP、区間 DP、bit DP という用語はプログラミングコンテスト界隈で広く用いられている俗称ですが、正式な学術用語ではないです。

オンラインジャッジのススメ

この記事で紹介する問題は主に、AtCoder Problems、AOJ、Topcoder SRM から集めています。これらのサイトにはアルゴリズム関連の問題が多数集められており、それぞれに対してソースコードを提出することができて、予め用意してある入力ケースすべてに正解を出力することができたら AC(Accepted) がもらえます。アルゴリズムを実際に実装すると理解がより深まるのでおススメです！登録方法や始め方は以下のページを参考にしていただければと思います。

• AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～
• 初心者向けのABCの問題傾向とその対策
• AIZU ONLINE JUDGE登録方法と使い方
• TopCoder導入解説（登録～SRM参加～プラグイン導入）
• はじめてのTopCoder Single Round Match

1 ナップサック DP とは

まずはナップサック問題から...と言いたいところなのですが、最初はもっと簡単な問題を考えてみましょう。

問題 1:　最大和問題

n$n$ 個の整数 a[0],a[1],…,a[n−1]$a[0],a[1],\dots ,a[n-1]$ が与えられる。これらの整数から何個かの整数を選んで総和をとったときの、総和の最大値を求めよ。また、何も選ばない場合の総和は 0 であるものとする。

【制約】
・1≤n≤10000$1\le n\le 10000$
・−1000≤a[i]≤1000$-1000\le a[i]\le 1000$

【数値例】
1)
　n=3$n=3$
　a=(7,−6,9)$a=(7,-6,9)$
　答え: 16 (7 と 9 を選べばよいです)

2)
　n$n$ = 2
　a=(−9,−16)$a=(-9,-16)$
　答え: 0 (何も選ばないのがよいです)

　
はい、既にお気づきの方が多いと思いますが、これは DP を使うまでもなく「正の値を全部足す」だけでよいです。しかし、この問題を敢えて DP で書いてみることで DP に慣れようという企画です。

　
【解法】
dp[0]$\mathrm{d}\mathrm{p}[0]$ := 何も選ばない状態
dp[1]$\mathrm{d}\mathrm{p}[1]$ := 0 番目までの整数 (a$a$[0] のみ) の中から整数を選んで総和をとったときの、総和の最大値
dp[2]$\mathrm{d}\mathrm{p}[2]$ := 1 番目までの整数 (a[0],a[1]$a[0],a[1]$) の中から整数を選んで総和をとったときの、総和の最大値
…
dp[i+1]$\mathrm{d}\mathrm{p}[\mathrm{i}+1]$ := i$i$ 番目までの整数 (a[0],…,a[i]$a[0],\dots ,a[i]$) の中から整数を選んで総和をとったときの、総和の最大値
とします。
求める値は、dp[n]$\mathrm{d}\mathrm{p}[\mathrm{n}]$ です。

既に dp[i]$\mathrm{d}\mathrm{p}[\mathrm{i}]$ の値が求まっていることを前提に、dp[i+1]$\mathrm{d}\mathrm{p}[\mathrm{i}+1]$ の値を求めることを考えます。
dp[i]$\mathrm{d}\mathrm{p}[\mathrm{i}]$ を使って dp[i+1]$\mathrm{d}\mathrm{p}[\mathrm{i}+1]$ について考えるとき、a[0],a[1],…,a[i−1]$a[0],a[1],\dots ,a[i-1]$ のどれを選んだらよいかが既に決まっているので、a[i]$a[i]$ を選ぶか選ばないかだけ決めればよいです。

• 選ぶとき　　: dp[i]$\mathrm{d}\mathrm{p}[\mathrm{i}]$ に a[i]$a[i]$ が加算されるので、dp[i+1]=dp[i]+a[i]$\mathrm{d}\mathrm{p}[\mathrm{i}+1]=\mathrm{d}\mathrm{p}[\mathrm{i}]+\mathrm{a}[\mathrm{i}]$ です
• 選ばないとき: dp[i]$\mathrm{d}\mathrm{p}[\mathrm{i}]$ は特に何も加算されないので、dp[i+1]=dp[i]$\mathrm{d}\mathrm{p}[\mathrm{i}+1]=\mathrm{d}\mathrm{p}[\mathrm{i}]$ です

これらをまとめると、以下のようになります。

＜DP遷移式＞

数学で言うところの漸化式と一緒ですね。遷移していくためには、初期値が必要です。初期値は

＜初期値＞

です。あとは、以上のことをC++言語で書いてあげると、以下のようになります。

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

// 入力
int n;
int a[10010];  // 最大10000個ですが、少しだけ多めにとります

// DP テーブル
int dp[10010];


int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];

    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
        dp[i + 1] = max(dp[i], dp[i] + a[i]);
    }

    cout << dp[n] << endl;
}

プログラミング作法についてはここでは問わないことにします。
さて、いよいよ次からナップサック問題を考えてみましょう。

2 ナップサック問題

ナップサック問題の登場までが長くなってしまいましたが、本来 DP 以外で簡単に解ける問題を敢えて DP で解いたのは、ナップサック問題に対する DP はこれよりも一段難易度が上がるからです。実際に解いてみましょう！

なお、このナップサック問題は、
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp
でソースコードを提出してジャッジできます。実際にソースコードを記述して提出してみると理解が深まると思います。
　

問題 2:　ナップサック問題

n$n$ 個の品物があり、i$i$ 番目の品物のそれぞれ重さと価値が weight[i],value[i]$\mathrm{w}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}[\mathrm{i}],\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}[\mathrm{i}]$ となっている (i=0,1,...,n−1$i=0,1,...,n-1$)。
これらの品物から重さの総和が W$W$ を超えないように選んだときの、価値の総和の最大値を求めよ。

【制約】
・1≤n≤100$1\le n\le 100$
・weight[i],value[i]$\mathrm{w}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}[\mathrm{i}],\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}[\mathrm{i}]$ は整数
・1≤weight[i],value[i]≤1000$1\le \mathrm{w}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}[\mathrm{i}],\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}[\mathrm{i}]\le 1000$
・1≤W≤10000$1\le W\le 10000$

【数値例】
1)
　n=6$n=6$
　(weight,value)=(2,3),(1,2),(3,6),(2,1),(1,3),(5,85)$(\mathrm{w}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t},\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e})=(2,3),(1,2),(3,6),(2,1),(1,3),(5,85)$
　W=9$W=9$
　答え: 94 ((3,6), (1,3), (5,85) を選んだときが最大です)

　
さっきの問題が「価値」だけだったのに対し、「重さ」が加わった感じですね。基本的に、重さに対する価値の比率 value[i]/weight[i]$\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}[\mathrm{i}]/\mathrm{w}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}[\mathrm{i}]$ が大きいものを選んでいきたいわけですが、単に「value[i]/weight[i]$\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}[\mathrm{i}]/\mathrm{w}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}[\mathrm{i}]$ が大きい順にソートして、重さが W$W$ を超えないギリギリまで詰める」という方針では最適解になるとは限らないです。上の数値例もその反例となっています。

　
【解法】
さっきと同じようにやります。しかし、完全にさっきと同じように

dp[i+1]:=i$\mathrm{d}\mathrm{p}[\mathrm{i}+1]:=\mathrm{i}$ 番目までの品物の中から重さが W$W$ を超えないように選んだときの、価値の総和の最大値

としてしまうと詰まってしまいます。dp[i+1]$\mathrm{d}\mathrm{p}[\mathrm{i}+1]$ を考えるときに、dp[i]$\mathrm{d}\mathrm{p}[\mathrm{i}]$ に対して品物 (weight[i],value[i])$(\mathrm{w}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}[\mathrm{i}],\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}[\mathrm{i}])$ を加えるか否かを考えるわけだが、加えたときに重さが W$W$ を超えてしまうのかどうかがわからないという問題が起こります。dp[i]$\mathrm{d}\mathrm{p}[\mathrm{i}]$ に対して、「今重さがどうなっているか」という情報が必要なのです。そこで少し修正して以下のようにします:

dp[i+1][w]$\mathrm{d}\mathrm{p}[\mathrm{i}+1][\mathrm{w}]$ := i$i$ 番目までの品物の中から重さが w$w$ を超えないように選んだときの、価値の総和の最大値

そして先程は dp[i]$\mathrm{d}\mathrm{p}[\mathrm{i}]$ の値が求まっていることを前提にして dp[i+1]$\mathrm{d}\mathrm{p}[\mathrm{i}+1]$ の値を考えたわけですが、今回は dp[i][w](w=0,1,…,W)$\mathrm{d}\mathrm{p}[\mathrm{i}][\mathrm{w}](\mathrm{w}=0,1,\dots ,\mathrm{W})$ の値が求まっていることを前提にして、dp[i+1][w](w=0,1,…,W)$\mathrm{d}\mathrm{p}[\mathrm{i}+1][\mathrm{w}](\mathrm{w}=0,1,\dots ,\mathrm{W})$ の値を考えてみます。

dp[i+1][w]$\mathrm{d}\mathrm{p}[\mathrm{i}+1][\mathrm{w}]$ の値を求めるには、以下のうち大きい方をとります:

• 品物 (weight[i],value[i])$(\mathrm{w}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}[\mathrm{i}],\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}[\mathrm{i}])$ を選ぶ場合 (w≥weight[i]$w\ge \mathrm{w}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}[\mathrm{i}]$ の場合のみ)
  

  dp[i+1][w]=dp[i][w−weight[i]]+value[i]$$\mathrm{d}\mathrm{p}[\mathrm{i}+1][\mathrm{w}]=\mathrm{d}\mathrm{p}[\mathrm{i}][\mathrm{w}-\mathrm{w}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}[\mathrm{i}]]+\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}[\mathrm{i}]$$

• 品物 (weight[i],value[i])$(\mathrm{w}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}[\mathrm{i}],\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}[\mathrm{i}])$ を選ばない場合
  

  dp[i+1][w]=dp[i][w]$$\mathrm{d}\mathrm{p}[\mathrm{i}+1][\mathrm{w}]=\mathrm{d}\mathrm{p}[\mathrm{i}][\mathrm{w}]$$

まとめると、以下のようになります。

＜DP漸化式＞

<DP初期条件＞

「問題1: 最大和問題」に比べると、dp テーブルの添字が 1 個から 2 個に増えた分、少しだけ難易度が上がりました。実際に DP を設計するときに、「これだけじゃ情報が足りない -> 添字を付け足す」というのは非常によく行います。
これを素直に C++ で実装すると以下のようになります。

#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

// 入力
int n, W;
int weight[110], value[110];

// DPテーブル
int dp[110][10010];

int main() {
  cin >> n >> W;
  for (int i = 0; i < n; ++i) cin >> value[i] >> weight[i];

  // DP初期条件: dp[0][w] = 0
  for (int w = 0; w <= W; ++w) dp[0][w] = 0;

  // DPループ
  for (int i = 0; i < n; ++i) {
    for (int w = 0; w <= W; ++w) {
      if (w >= weight[i]) dp[i+1][w] = max(dp[i][w-weight[i]] + value[i], dp[i][w]);
      else dp[i+1][w] = dp[i][w];
    }
  }

  cout << dp[n][W] << endl;
}

なお、このナップサック問題に対する DP について、実際にテーブル値が更新される様子は下図のようになります ((weight,value)=(2,3),(1,2),(3,6),(2,1),(1,3),(5,85)$(\mathrm{w}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t},\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e})=(2,3),(1,2),(3,6),(2,1),(1,3),(5,85)$ の場合)。

3 部分和問題とその応用たち

さて、DP で解ける問題は最適化問題だけではありません。ナップサック問題とよく似た問題として、次の部分和問題も有名です。むしろ、この部分和問題の方が簡単な問題です (部分和問題の方が簡単な問題で、部分和問題が NP-complete だから、ナップサック問題が NP-hard であることが示される、という話もあったりします)。
　

問題 3:　部分和問題　

n$n$ 個の正の整数 a[0],a[1],…,a[n−1]$a[0],a[1],\dots ,a[n-1]$ と正の整数 A$A$ が与えられる。これらの整数から何個かの整数を選んで総和が A$A$ になるようにすることが可能か判定せよ。可能ならば "YES" と出力し、不可能ならば "NO" と出力せよ。

【制約】
・1≤n≤100$1\le n\le 100$
・1≤a[i]≤1000$1\le a[i]\le 1000$
・1≤A≤10000$1\le A\le 10000$

【数値例】
1)
　n=3$n=3$
　a=(7,5,3)$a=(7,5,3)$
　A=10$A=10$
　答え: YES (7 と 3 を選べばよいです)

2)
　n$n$ = 2
　a=(9,7)$a=(9,7)$
　A=6$A=6$
　答え: NO

　
【解法】
ナップサック問題とほぼ一緒です。
dp[i+1][j]$\mathrm{d}\mathrm{p}[\mathrm{i}+1][\mathrm{j}]$ := i$i$ 番目までの整数の中からいくつか選んで総和を j$j$ とすることが可能かどうか (bool値)
として、dp[i][j](j=0,1,…,A)$\mathrm{d}\mathrm{p}[\mathrm{i}][\mathrm{j}](\mathrm{j}=0,1,\dots ,\mathrm{A})$ を使って dp[i+1][j](j=0,1,…,A)$\mathrm{d}\mathrm{p}[\mathrm{i}+1][\mathrm{j}](\mathrm{j}=0,1,\dots ,\mathrm{A})$ の値を更新することを考えます。

dp[i+1][j]$\mathrm{d}\mathrm{p}[\mathrm{i}+1][\mathrm{j}]$ の値を求めるには、以下のようになります。

• 整数 a[i]$a[i]$ を選ぶ場合 (j≥a[i]$j\ge a[i]$ の場合のみ)
  

  dp[i][j−a[i]]　が　True　なら、dp[i+1][j]　も　True$$\mathrm{d}\mathrm{p}[\mathrm{i}][\mathrm{j}-\mathrm{a}[\mathrm{i}]] が \mathrm{T}\mathrm{r}\mathrm{u}\mathrm{e} なら、\mathrm{d}\mathrm{p}[\mathrm{i}+1][\mathrm{j}] も \mathrm{T}\mathrm{r}\mathrm{u}\mathrm{e}$$

• 整数 a[i]$a[i]$ を選ばない場合
  

  dp[i][j]　が　True　なら、dp[i+1][j]　も　True$$\mathrm{d}\mathrm{p}[\mathrm{i}][\mathrm{j}] が \mathrm{T}\mathrm{r}\mathrm{u}\mathrm{e} なら、\mathrm{d}\mathrm{p}[\mathrm{i}+1][\mathrm{j}] も \mathrm{T}\mathrm{r}\mathrm{u}\mathrm{e}$$

まとめると、以下のようになります。

＜DP漸化式＞

<DP初期条件＞

(0 個の整数の和は 0 とみなせるので、dp[0][0]$\mathrm{d}\mathrm{p}[0][0]$ のみ True$\mathrm{T}\mathrm{r}\mathrm{u}\mathrm{e}$ です)

ここで、| は or 演算子です。ソースコードにすると、以下のようになります。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

// 入力
int n, A;
int a[110];

// DPテーブル
bool dp[110][10010];

int main() {
  cin >> n >> A;
  for (int i = 0; i < n; ++i) cin >> a[i];

  memset(dp, 0, sizeof(dp));   // 一旦すべて false に
  dp[0][0] = true;             // dp[0][0] だけ true に

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= A; ++j) {
      dp[i+1][j] |= dp[i][j];
      if (j >= a[i]) dp[i+1][j] |= dp[i][j-a[i]];
    }
  }

  if (dp[n][A]) cout << "YES" << endl;
  else cout << "NO" << endl;
}

さて、この部分和問題は「A を作れますか？」という判定問題でしたが、DP はもう少し賢いこともできます。ちょっと賢くして「A を作る方法は何通りありますか？」という問題をやってみましょう！

問題 4:　部分和数え上げ問題　

n$n$ 個の正の整数 a[0],a[1],…,a[n−1]$a[0],a[1],\dots ,a[n-1]$ と正の整数 A$A$ が与えられる。これらの整数から何個かの整数を選んで総和が A$A$ になるようにする方法が何通りあるかを求めよ。ただし、答えがとても大きくなる可能性があるので、1,000,000,009 で割った余りで出力せよ。

【制約】
・1≤n≤100$1\le n\le 100$
・1≤a[i]≤1000$1\le a[i]\le 1000$
・1≤A≤10000$1\le A\le 10000$

【数値例】
1)
　n=5$n=5$
　a=(7,5,3,1,8)$a=(7,5,3,1,8)$
　A=12$A=12$
　答え: 2 ((7と5), (3と1と8) の 2 通りがあります)

2)
　n=4$n=4$
　a=(4,1,1,1)$a=(4,1,1,1)$
　A=5$A=5$
　答え: 3 ((4, 1), (4, 1), (4, 1) の 3 通りがあります。同じ 1 でも index が違うものは異なる組合わせとみなします)

部分和問題にほんの少しの変更を付け加えるだけです。
dp[i+1][j]$\mathrm{d}\mathrm{p}[\mathrm{i}+1][\mathrm{j}]$ := i$i$ 番目までの整数の中からいくつか選んで総和を j$j$ とする場合の数
として、dp[i+1][j]$\mathrm{d}\mathrm{p}[\mathrm{i}+1][\mathrm{j}]$ の値を求めるには、以下の 2 つの場合を加算します。

• 整数 a[i]$a[i]$ を選ぶ場合 (j≥a[i]$j\ge a[i]$ の場合のみ)
  

  dp[i][j−a[i]]通り$$\mathrm{d}\mathrm{p}[\mathrm{i}][\mathrm{j}-\mathrm{a}[\mathrm{i}]]通り$$

• 整数 a[i]$a[i]$ を選ばない場合
  

  dp[i][j]通り$$\mathrm{d}\mathrm{p}[\mathrm{i}][\mathrm{j}]通り$$

まとめると、以下のようになります。

＜DP漸化式＞

<DP初期条件＞

(0 個の整数の和は 0 とみなせるので、dp[0][0]$\mathrm{d}\mathrm{p}[0][0]$ のみ 1 通りです)

ソースコードにすると以下の通りです。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MOD = 1000000009;

// 入力
int n, A;
int a[110];

// DPテーブル
int dp[110][10010];

int main() {
  cin >> n >> A;
  for (int i = 0; i < n; ++i) cin >> a[i];

  memset(dp, 0, sizeof(dp));   // 一旦すべて 0 に
  dp[0][0] = 1;                // dp[0][0] だけ 1 に

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= A; ++j) {
      (dp[i+1][j] += dp[i][j]) %= MOD;
      if (j >= a[i]) (dp[i+1][j] += dp[i][j-a[i]]) %= MOD;
    }
  }

  cout << dp[n][A] << endl;
}

さらに、以下のような問題も考えられます。

問題 5:　最小個数部分和問題　

n$n$ 個の正の整数 a[0],a[1],…,a[n−1]$a[0],a[1],\dots ,a[n-1]$ と正の整数 A$A$ が与えられる。これらの整数から何個かの整数を選んで総和が A$A$ にする方法をすべて考えた時、選ぶ整数の個数の最小値を求めよ。A$A$ にすることができない場合は -1 と出力せよ。

【制約】
・1≤n≤100$1\le n\le 100$
・1≤a[i]≤1000$1\le a[i]\le 1000$
・1≤A≤10000$1\le A\le 10000$

【数値例】
1)
　n=5$n=5$
　a=(7,5,3,1,8)$a=(7,5,3,1,8)$
　A=12$A=12$
　答え: 2 ((7, 5)と(3, 1, 8)とがありますが、(7, 5) の2個が最小です)

2)
　n=2$n=2$
　a=(7,5)$a=(7,5)$
　A=6$A=6$
　答え: -1

　
【解法】

dp[i+1][j]$\mathrm{d}\mathrm{p}[\mathrm{i}+1][\mathrm{j}]$ := i$i$ 番目までの整数の中からいくつかの整数を選んで総和が j$j$ とする方法をすべて考えたときの、選んだ整数の個数の最小値

とすると、dp[i+1][j]$\mathrm{d}\mathrm{p}[\mathrm{i}+1][\mathrm{j}]$ の値を求めるには、以下の 2 つの場合の minimum をとります。

• 整数 a[i]$a[i]$ を選ぶ場合 (j≥a[i]$j\ge a[i]$ の場合のみ)
  

  dp[i][j−a[i]]+1$$\mathrm{d}\mathrm{p}[\mathrm{i}][\mathrm{j}-\mathrm{a}[\mathrm{i}]]+1$$

• 整数 a[i]$a[i]$ を選ばない場合
  

  dp[i][j]$$\mathrm{d}\mathrm{p}[\mathrm{i}][\mathrm{j}]$$

まとめると、以下のようになります。

＜DP漸化式＞

<DP初期条件＞

(0 個の整数の和は 0 とみなせるので、dp[0][0]$\mathrm{d}\mathrm{p}[0][0]$ のみ 0 個です。)

ソースコードにすると、以下のようになります。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 1<<29;        // 十分大きい値にする, INT_MAX にしないのはオーバーフロー対策

// 入力
int n, A;
int a[110];

// DPテーブル
int dp[110][10010];

int main() {
  cin >> n >> A;
  for (int i = 0; i < n; ++i) cin >> a[i];

  // 一旦すべて INF に
  for (int i = 0; i < 110; ++i) for (int j = 0; j < 10010; ++j) dp[i][j] = INF;
  dp[0][0] = 0;                // dp[0][0] だけ 0 に

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= A; ++j) {
      dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
      if (j >= a[i]) dp[i+1][j] = min(dp[i+1][j], dp[i][j-a[i]] + 1);
    }
  }

  if (dp[n][A] < INF) cout << dp[n][A] << endl;
  else cout << -1 << endl;
}

最後に、発展問題として、以下の問題を考えてみましょう。重要な教訓が1つ得られる問題です。

問題 6:　K個以内部分和問題

n$n$ 個の正の整数 a[0],a[1],…,a[n−1]$a[0],a[1],\dots ,a[n-1]$ と正の整数 A$A$ が与えられる。これらの整数から K$K$ 個以内の整数を選んで総和が A$A$ になるようにすることが可能か判定せよ。可能ならば "YES" と出力し、不可能ならば "NO" と出力せよ。

【制約】
・1≤K≤n≤500$1\le K\le n\le 500$
・1≤a[i]≤1000$1\le a[i]\le 1000$
・1≤A≤10000$1\le A\le 10000$

【数値例】
1)
　n=3$n=3$
　K=2$K=2$
　a=(7,5,3)$a=(7,5,3)$
　A=10$A=10$
　答え: YES (7 と 3 を選べばよいです)

2)
　n=3$n=3$
　K=1$K=1$
　a=(7,5,3)$a=(7,5,3)$
　A=10$A=10$
　答え: NO

【解法】
問題3 (部分和問題) に対して、K$K$ 個以内という制約が加わりました。問題3 のように

dp[i+1][j]$\mathrm{d}\mathrm{p}[\mathrm{i}+1][\mathrm{j}]$ := i$i$ 番目までの整数の中からいくつか選んで総和を j$j$ とすることが可能かどうか

として、dp[i][j]$\mathrm{d}\mathrm{p}[\mathrm{i}][\mathrm{j}]$ を使って dp[i+1][j]$\mathrm{d}\mathrm{p}[\mathrm{i}+1][\mathrm{j}]$ の値を更新することを考えると、既に何個選んだかの情報がないので a[i]$a[i]$ を選ぶことにしたときに K$K$ 個を超えてしまうかどうかがわかりません。そこで、次のようにしたくなります。このように添字を付け加えて DP を設計すること自体はとても重要なテクニックです。

dp[i+1][j][k]$\mathrm{d}\mathrm{p}[\mathrm{i}+1][\mathrm{j}][\mathrm{k}]$ := i$i$ 番目までの整数の中から k$k$ 個の整数を選んで足した総和が j$j$ とすることが可能かどうか

こうすることで、確かにこの問題を解くことのできるアルゴリズムを構成することができます。しかし、このとき計算時間はどのようになるでしょうか。DP テーブルのサイズは、nKA$nKA$ となり、実際のアルゴリズムの計算時間も O(nKA)$O(nKA)$ となります。もしこのオーダーで間に合うような制約であればいいのですが、今回はこれでは間に合いません。そこで、「DP の添字ではなく、DP の値そのものに情報をもたせられないか」と考えてみましょう。プログラミングコンテストチャレンジブック第二版 P.63にもある通り、一般に bool 値を求める DP をすることは無駄であることが多く、同じ計算量でもっと多くのことを知ることができます。
具体的には次のようにしてみましょう。

dp[i+1][j]$\mathrm{d}\mathrm{p}[\mathrm{i}+1][\mathrm{j}]$ := i$i$ 番目までの整数の中からいくつかの整数を選んで総和が j$j$ とする方法をすべて考えたときの、選んだ整数の個数の最小値

これは実は問題 5 (最小個数部分和問題) で立てる DP そのものですね。問題 5 と同じようにテーブルを作っておけば、最後答えを出力するときに

• dp[n][A]≤K$\mathrm{d}\mathrm{p}[\mathrm{n}][\mathrm{A}]\le \mathrm{K}$ ならば "YES"
• dp[n][A]>K$\mathrm{d}\mathrm{p}[\mathrm{n}][\mathrm{A}]>\mathrm{K}$ ならば "NO"

とすればよいです。これならば計算時間オーダーは、O(NA)$O(NA)$ で求めることができます。

このテクニックを推し進めると、以下の問題もオーダー O(NA)$O(NA)$ で解くことができます。解説はプログラミングコンテストチャレンジブック第二版 P.62～P.63にありますので、是非考えてみると面白いと思います。

問題 7:　個数制限付き部分和問題

n$n$ 種類の正の整数 a[0],a[1],…,a[n−1]$a[0],a[1],\dots ,a[n-1]$ がそれぞれ m[i]$m[i]$ 個ずつある。また、正の整数 A$A$ が与えられる。これらの整数からいくつか選んで総和が A$A$ になるようにすることが可能か判定せよ。可能ならば "YES" と出力し、不可能ならば "NO" と出力せよ。

【制約】
・1≤n≤500$1\le n\le 500$
・1≤a[i],m[i]≤10000$1\le a[i],m[i]\le 10000$
・1≤A≤10000$1\le A\le 10000$