アルゴリズムのお勉強（３）- 動的計画法(DP) : ボトムアップ形式

f:id:robonchu:20190610003125p:plain — http://theoryofprogramming.com/2015/03/02/dynamic-programming-introduction-and-fibonacci-numbers/

やりたいこと

動的計画法（DP）について学ぶ。
トップダウン形式とボトムアップ形式と2種類のDPのうち、今回はボトムアップ形式の説明。

動的計画法とは

以下動的計画法 - Wikipediaから抜粋。

細かくアルゴリズムが定義されているわけではなく、下記2条件を満たすアルゴリズムの総称である。
1. 帰納的な関係の利用：より小さな問題例の解や計算結果を帰納的な関係を利用してより大きな問題例を解くのに使用する。
2. 計算結果の記録：小さな問題例、計算結果から記録し、同じ計算を何度も行うことを避ける。

今回着目するのは1番の方。漸化式で解ける。

例題を解きながらコーディングのイメージがつかめるわかりやすい説明。感謝です。
- 動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集 - Qiita
イラスト付きでわかりやすく説明されているもの。感謝です。
- プログラミングコンテストでの動的計画法

ボトムアップ形式のDPを使ってとく例題

atcoder.jp

AtCoder Beginner Contest 129のC問題より抜粋

問題: C - Typical Stairs

f:id:robonchu:20190610005349p:plain

入力

f:id:robonchu:20190610005526p:plain

出力

f:id:robonchu:20190610005700p:plain

制約

f:id:robonchu:20190610005639p:plain

入力/出力例

入力

6 1
3

出力

移動方法は以下の 4通りです。

0→1→2→4→5→6
0→1→2→4→6
0→2→4→5→6
0→2→4→6

解き方

以下の漸化式を用いて壊れた床の場合はスキップすることで解ける。

f:id:robonchu:20190610010827p:plain

x段目にたどり着く方法はx-1から一歩で上がるか、x-2から二歩であがるかの二通りだから。

ボトムアップ形式のDPを使った実装例(C++)

解説記事のコードがわかりやすかったので、抜粋 + 解説コメント付与。
動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集 - Qiitaさんのわかりやすいイメージ図を抜粋。値は違うが考え方は同じ。

f:id:robonchu:20190610010157p:plain

#include <iostream>
#include <vector>

using namespace std;
const long long mod=1e9+7;
 
int main(){
  int N, M;
  cin >> N >> M;
 
  //  0段目があるので、N+1の配列を用意し、
  //  壊れていない階段をtrue=1、壊れている階段をfalse=0で初期化。
  //  これを使ってスキップの処理を行う。
  vector<int> oks(N + 1, true);
  for(int i = 0; i < M; ++i) {
    int a;
    cin >> a;
    oks[a] = false;
  }

  //  0~N段目までの"通り数"を入れる配列
  vector<long long int> dp(N + 1);

  //  0段目を1で初期化
  dp[0] = 1;
 
  for(int now = 0; now < N; ++now){
    //  ここがポイント。
    //  階段が壊れていなければ、ここのfor loopはi = N - 1 を除いて二回、i = N - 1のときは一回実行される。
    //  この二回の実行の繰り返しによって上記の漸化式が実装でされることになる。
    //  以下に簡単なイメージ図を添付。  
    for(int next = now + 1; next <= min(N, now + 2); ++next){
      //  最初に作ったoks配列を用いることで壊れている床をスキップする。
      if (oks[next]) {
        //  漸化式。
        dp[next] += dp[now];

        //  期待される出力のためにmodで割る。
        dp[next] %= mod;
      }
     }
   }

   // 求めたいN番目の通り数を出力。
   cout << dp[N] << endl;
   return 0;
}