2019-09-18

はじめての DP の練習用問題まとめ～フィボナッチな DP ～

0. DP のはじめの一歩

ふと、人生で初めて「この問題は DP だよ」という状況に直面した方が、DP へのはじめの一歩を踏み出すのに良さそうな問題たちをまとめたくなった。

DP のはじめの一歩な問題として、どんな問題がふさわしいかについて、AtCoder Educational DP Contest A 問題が、一つの道筋を示している！！！

atcoder.jp

問題概要 (少し表現改)

$N$ 個の足場があって、 $i$ 番目の足場の高さは $h_i$ です。最初、足場 $0$ にカエルがいて、ぴょんぴょん跳ねながら足場 $N-1$ へと向かいます。カエルは足場 $i$ にいるときに

足場 $i$ から足場 $i+1$ へと移動する (そのコストは $|h_{i} - h_{i+1}|$ )
足場 $i$ から足場 $i+2$ へと移動する (そのコストは $|h_{i} - h_{i+2}|$ )

のいずれかの行動を選べます。カエルが足場 $0$ から足場 $N-1$ へと移動するのに必要な最小コストを求めよ。

f:id:drken1215:20190918153849p:plain

1. どんな DP？

たとえば上記の Frog 問題に対する詳しい解説は

qiita.com

に書いたので、そこを見てもらえれば...と思う。簡単にいうと、下図みたいな形をしているグラフ (頂点が順に並んでいて、各辺から「隣の頂点への辺」と「一個飛ばしの頂点への辺」が出ているようなグラフ) において、左から順番にノードの値を確定させていくような DP！！！

f:id:drken1215:20190918145138p:plain

こういう問題が出現する場面としては

階段や足場に対して「次の地点に行く」「一個飛ばしの地点に行く」という二通りの方法がある
1 × W の長方形を「1 × 1 の正方形」「1 × 2 の長方形」を使って敷き詰める

などが挙げられる。そして DP の遷移式は、以下のような雰囲気になる (これらの意味がわからなかったら、上の記事を)。

最小化問題の場合

dp[ i ] = min(dp[ i ], dp[ i - 1 ])
dp[ i ] = min(dp[ i ], dp[ i - 2 ])

最大化問題の場合

dp[ i ] = max(dp[ i ], dp[ i - 1 ])
dp[ i ] = max(dp[ i ], dp[ i - 2 ])

数え上げ問題の場合 (1000000007 で割ったあまりとか)

MOD = 1000000007 として

dp[ i ] = (dp[ i ] + dp[ i - 1 ]) % MOD
dp[ i ] = (dp[ i ] + dp[ i - 2 ]) % MOD

2. 問題集

このような DP の問題たちを挙げていきたい。何問か解くうちに慣れるはず！！

2-1. フィボナッチ数列

このような DP について、フィボナッチ数列を思い出した方は多いと思う。実際フィボナッチ数列とは

$F_{0} = 1$
$F_{1} = 1$
$F_{n} = F_{n-1} + F_{n-2}$

という漸化式で表されるもので、

$1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \dots$

と続いていく。これはまさに下図のようなグラフにおいて、頂点 0 から頂点 $n$ まで至る経路の本数を表している。つまり

$F_{n}$ = 下図のグラフで頂点 0 から頂点 $n$ まで至る経路の本数

なのだ。

f:id:drken1215:20190918145138p:plain

フィボナッチ数列を求めさせる問題は実は AOJ にある！！！

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_A&lang=ja

難しく考えずに、以下のコードで正解できる。ここで dp[ i ] の値が、フィボナッチ数列の第 i 項 ( $F_{i}$ を表す。

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

int main() {
    int n; cin >> n;

    // F[0] から F[n] までの分のメモリを確保
    // 初期値を 0 としておく
    vector<long long> dp(n + 1, 0);

    // 初期条件
    dp[0] = 1;
    dp[1] = 1;

    // DP の遷移を行う
    for (int i = 2; i <= n; ++i) {
        dp[i] += dp[i - 1];
        dp[i] += dp[i - 2];
    }

    // 答え
    cout << dp[n] << endl;
}

2-2. AtCoder EDPC A - Frog

先程紹介した Frog 問題。これも同じ構造をした DP。

https://atcoder.jp/contests/dp/tasks/dp_a

先程と遷移が良く似た DP で正解できる。

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1LL << 60;

// 入力
int N;
long long h[100010];

// DP テーブル
long long dp[100010];

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

    // 初期化 (最小化問題なので INF に初期化)
    for (int i = 0; i < 100010; ++i) dp[i] = INF;

    // 初期条件
    dp[0] = 0;

    // ループ
    for (int i = 1; i < N; ++i) {
        chmin(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]));
        if (i > 1) chmin(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]));
    }

    // 答え
    cout << dp[N-1] << endl;
}