動的計画法(DP)メモ_初心者向け

背景

最近アルゴリズムをたくさん勉強したのでメモしたい。
特に今まで意味不明の極みだった動的計画法を少し理解したので書きたい。

Qiitaでは色んな人がボトムアップ法について書いているので僕はボトムアップ法よりも理解しやすいトップダウン法(メモ化再帰とも)について書きたい。

以下に書くことは僕の個人的解釈なので、誤解していたりミスがあったらどしどし指摘していただきたい限りでござる。

動的計画法とは

動的計画法　≒　「漸化式」＋「解の保存」

この一言に尽きる。

例をあげて考えてみよう。

フィボナッチ数列

フィボナッチ数列は
$$ F_0 = 0, F_1 = 1 \\ F_n = F_{n-1} + F_{n-2} (n \geq 2) $$
によって定義される数列である。
この第$n$項を求めたい。まずはこの漸化式をそのままC言語で書いてみよう。

c

int fib(int n) {
    if (n <= 1) return n;
    else return fib(n - 1) + fib(n  - 2);
}

このアルゴリズムの計算量を考えてみよう。早くDPを知りたい人は飛ばしてかまわない。
計算量$T(n)$を「$F_n$を計算するためにアルゴリズムの中で実行する加算の回数」と定義すると、$T_n$は次の漸化式を満たす。
$$ T(0) = T(1) = 0\\ T(n) = T(n - 1) + T(n - 2) + 1 (n \geq 2) $$
この式を変形すると、$T(n) + 1 = F_{n+1}$となり$\phi = \frac{1 + \sqrt{5}}{2}$を用いて$T_n \fallingdotseq \frac{\phi^n}{\sqrt{5}}$と表され、指数関数的に大きくなってしまう。
これはとても効率が悪い。
もうすこし具体的に考えてみると、例えば$F_{10}$を計算するためには$F_9$と$F_8$を計算する必要があるが、$F_9$を計算するためにも$F_8$を計算しなければならなく、二度手間である。

そこで動的計画法の登場。動的計画法の基本的な考え方は、「計算結果を配列に保存しておいて無駄な計算の重複を避ける」ということである。
動的計画法を用いてC言語でフィボナッチ数を計算するアルゴリズムを書いてみよう。

c

int dp[N+1];  //解を保存する配列。main関数の中で、dp[0]=0,dp[1]=1,他のすべての要素に-1を代入しておく。

int fib(int n) {
  if (dp[n] != -1) return dp[n];  //計算済みの場合はそのまま配列の値を返す。
  dp[n] = fib(n - 1) + fib(n - 2);
  return dp[n];
}

まず、dp配列にまだ計算していないしるしとしてすべての要素に-1を代入しておく。
すでにわかっている項($F_0とF_1$)はわかっている値を代入する。
そして再帰的関係を用いて、まだ計算されていないならば計算し配列に保存しておく、すでに計算済みならばそのまま配列の値を返す、といった具合に計算してゆく。

といった流れになる。

これを用いてフィボナッチ数の$10$番目の数を求めるプログラムは以下になる。

c

#include <stdio.h>

# define N 1000    //適当に大きな値

int dp[N+1];  

int fib(int n) {
  if (dp[n] != -1) return dp[n];
  dp[n] = fib(n - 1) + fib(n - 2);
  return dp[n];
}

int main() {

    for(int i=0; i<=N; i++){        //全ての配列を-1で初期化
        dp[i] = -1;
    }
    dp[0] = 0;    //fib(0) = 0なので配列に解を省略しておく
    dp[1] = 1;    //fib(1) = 1なので配列に解を省略しておく

    printf("%d\n", fib(10));

    return 0;
}

結果

55

動的計画法を用いて解を保存していくと、ある$n$に対して$T(n)$はただ1度のみ計算される。
またdp配列の初期化に$O(n)$かかるので、全体的な計算量はこの場合は$O(n)$となる。

最初に示したプログラムが約$O(\phi^n)$だったので、非常に早く計算できるアルゴリズムということがわかる。

ちなみに漸化式を止めるには必ず初項($T(0), T(1)$)が必要なので忘れないようにしよう。

もう少し一般的な動的計画法

さて、フィボナッチ数列の場合は定義式がそのまま漸化式になっていたが、一般的にはそうとは限らない。一般的には以下に見るよう「補助問題」を定義する必要がある。
自然数nに対する分割数$p(n)$を、「$n$を自然数の和として表現する方法の個数(順番の違いは同一視する)」と定義する。例えば、$n=5$の場合、
$$ 1+1+1+1+1, 1+1+1+2, 1+1+3,\\1+4, 5, 1+2+2, 2+3 $$
の7通りの表し方があるので$p(5) = 7$である。この分割数を計算するアルゴリズムを考えてみよう。
フィボナッチ数と違って分割数は再帰的に定義されていないし、漸化式を持つとも思えない。そこで元の問題に対する「補助問題」を定義する。分割数の場合、補助関数として$q(k,n)=$「k以下の数だけを使ったnの分割数」と定義する。すると
$$
\begin{align*}
q(1,n) &= 1,& n \ge 1\\
q(k,n) &= q(n,n),& k > n\ge 1\\
q(k,n) &= q(k-1,n) + 1,& k = n\ge 2\\
q(k,n) &= q(k-1,n) + q(k, n-k),& n> k\ge 2
\end{align*}
$$

という漸化式が成立する。「再帰は1じゃなくて0で止める」の経験則でkとnが0の場合に拡張すると
$$
\begin{align*}
q(0,0) &= 1,\\
q(0,n) &= 0,& n \ge 1\\
q(k,n) &= q(n,n),& k > n\ge 0\\
q(k,n) &= q(k-1,n) + q(k, n-k),& n\ge k\ge 1
\end{align*}
$$

が得られる。
求めたい$p(n) = q(n, n)$であるので、この漸化式を用いてフィボナッチ数のときと同じように再帰関数を作り$q(n, n)$を計算することができる。

一般的に補助問題を定義する時は

(1)補助問題の解から元の問題が効率良く解ける。
(2)補助問題の解の間に漸化式が成立する。

という2つの条件を満たすようにする必要がある。
実のところ、補助問題を定義するのが動的計画法で最も難しいところかもしれない。ひとたび補助問題が定義できれば、後は機械的に補助問題の解を再帰的関係を用いて計算できる。

それはそうととにかく上の分割数を求めるアルゴリズムをc言語で書いてみる。

int dp[N+1][N+1];    //解を保存する配列。main関数の中で全てに-1を代入しておく

int q(int k, int n){
  if(dp[k][n] != -1) return dp[k][n];    //計算済みの場合は配列の値を返す
//そうでない場合は計算結果を配列に保存しておく
  if(k == 0 && n == 0) dp[k][n] = 1;
  else if(k == 0) dp[k][n] = 0;
  else if(k > n) dp[k][n] = q(n, n);
  else dp[k][n] = q(k - 1, n) + q(k, n - k);
  return dp[k][n];
}

上のプログラムには書かれていないが、main関数の中で配列の中身を全て-1で初期化する必要がある。もう少し工夫して$k=0$の場合の解をあらかじめmain関数の中で保存しておくと、プログラムは次のようになる。

#include <stdio.h>

#define N 1000

unsigned long long int dp[N+1][N+1];

unsigned long long int q(int k, int n) {
    if(dp[k][n] != -1) return dp[k][n];     //計算済みの場合は配列の値を返す
    if(k > n) dp[k][n] = q(n, n);
    else dp[k][n] = q(k - 1, n) + q(k, n - k);
    return dp[k][n];
}

int main() {
    int n;

    scanf("%d", &n);

    dp[0][0] = 1;       //q(0,0)=0なので配列に解を保存しておく

    for(int i=1; i<=n; i++){        //q(0,n)=0なので配列に解を保存しておく
        dp[0][i] = 0;
    }

    for(int i=1; i<=n; i++){        //それ以外の場合は未計算なので「しるし」として-1を代入しておく
        for(int j=0; j<=n; j++){
            dp[i][j] = -1;
        }
    }

    printf("%llu\n", q(n, n));

    return 0;
}

非常にシンプルではなかろうか。動的計画法なんて「補助問題を定義して漸化式さえ立てられれば」簡単に書けてしまうのだ！！
ちなみに計算量はdp配列の初期化に$O(n^2)$かかり、dp配列を1つ埋めるのに高々1回の計算をするために全体として$O(n^2)$となる。

ナップザック問題

最後に、動的計画法といえばコレ！なナップザック問題を触っておこう。

$n$個ある荷物のうちいくつかをナップザックに入れて持って帰りたい。
$i=1,\dotsc,n$について$i$番目の荷物は価値が$p_i$であり、サイズが$w_i$である。
ナップザックに入れる荷物のサイズの和は$W$以下でなくてはならない。
このとき、ナップザックに入れることのできる荷物の選び方について価値の和の最大値$X$と対応する荷物$(N_1,N_2,\dotsc,N_m)$を求めよ。

制約
$$
1≤n≤100\\
1≤W≤10^5\\
1≤w_i≤W\\
1≤p_i≤10^9
$$

(Atcoder DPまとめコンテスト D-Knapsack1を参考にしました。)

この問題を解くための補助関数を

$q(k, w)$ =「$1$番目から$k$番目までの荷物を使ってサイズの和$w$以下で得られる価値の和の最大値」

と定義する。そうすると、$q(n, W) = X$である。この補助関数の漸化式を立ててみると、

\begin{equation*}
q(k, w) = \begin{cases}
0, &\text{if } k = 0\\
q(k-1, w), &\text{if } w < w_k\\
\max\left\{q(k-1, w), q(k-1, w-w_k) + p_k\right\}, &\text{otherwise.}
\end{cases}
\end{equation*}

となる。これをそのままC言語プログラムにすれば良い。

#include <stdio.h>

long long W[101];
long long P[101];

long long dp[101][100001];

long long max(long long a, long long b) {
    if (a >= b) return a;
    else return b;
}

long long q (int k, long long w) {
    if (dp[k][w] != -1) return dp[k][w];
    if (k == 0) dp[k][w] = 0;
    else if (w < W[k]) dp[k][w] = q(k-1, w);
    else {
        dp[k][w] = max(P[k] + q(k-1, w - W[k]), q(k-1, w));
    } 
    return dp[k][w];
}

int main() {

    long long n, M;
    scanf("%lld%lld", &n, &M);

    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld", &W[i], &P[i]);
    }


    for (int i = 0; i <= n; i++) {
        for (long long j = 0; j <= M; j++) {
            dp[i][j] = -1;
        }
    }

    printf("%lld\n", q(n, M));


    return 0;
}

計算量は$O(nW)$時間で求まる。
何度も言うが、「補助問題を定義して漸化式さえ立てられれば」動的計画法は簡単に書けてしまう。

終わりに

以上に書いたことは動的計画法の中でも簡単な、トップダウン法である。
トップダウン法とボトムアップ法では、時間計算量のオーダーは変わらないが、ボトムアップ法のほうが高速に計算できることが多い。また、ボトムアップ法は工夫することで空間計算量(使用するメモリ量のこと)が改善できる場合があるので、他の強い人の記事を見て勉強してほしい。

参考