動的計画法入門

読了目安 約3分

再帰の爆発をメモ化と DP テーブルで解消し、階段と最小コストの典型に進む。

動的計画法 (以後 DP) は、小さい問題の答えを記録し、再利用しながら大きい問題を解く手法です。

再帰は爆発する

フィボナッチ数列 (0, 1 から始め、前の 2 つの和を並べた数列) を素朴な再帰で計算してみます。

var calls = 0
func fib(_ n: Int) -> Int {
    calls += 1
    if n <= 1 { return n }
    return fib(n - 1) + fib(n - 2)
}
print(fib(25))
print("呼び出し回数: \(calls)")

25 番目だけで呼び出しは 24 万回を超えます。 fib(24) と fib(23) のどちらも fib(22) を呼ぶように、同じ計算が何度も走るからです。 n を 1 増やすごとに回数は約 1.6 倍になり、fib(50) は数百億回になって終わりません。

メモ化

一度出た答えを配列に記録し、再計算を避ける工夫をメモ化と呼びます。

var memo = [Int](repeating: -1, count: 61)
var calls = 0
func fib(_ n: Int) -> Int {
    calls += 1
    if n <= 1 { return n }
    if memo[n] != -1 { return memo[n] }
    memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]
}
print(fib(60))
print("呼び出し回数: \(calls)")

各 n の計算は 1 回だけになり、60 番目でも呼び出しは 119 回で済みます。

DP テーブル

再帰を使わず、小さい方から順に配列を埋めても同じ答えが出ます。

let n = 60
var dp = [Int](repeating: 0, count: n + 1)
dp[0] = 0
dp[1] = 1
for i in 2...n {
    dp[i] = dp[i - 1] + dp[i - 2]
}
print(dp[n])

この書き方の部品には名前があります。

• DP テーブル：小さい問題の答えを並べた配列 dp
• 遷移：埋まった要素から次の要素を作る式 dp[i] = dp[i - 1] + dp[i - 2]
• 初期条件：遷移の出発点になる値 dp[0] と dp[1]

DP の問題を解くことは、この 3 つを決めることです。

試してみよう: n を 92 に変えても一瞬で終わることを確かめてください (93 はオーバーフローします)。

典型 1: 階段の上り方

階段を 1 歩で 1 段または 2 段上るとき、N 段目までの上り方を数えます。

i 段目に来る直前にいるのは、i - 1 段目か i - 2 段目です。 「i 段目までの上り方」を dp[i] とすると、遷移は dp[i] = dp[i - 1] + dp[i - 2] になります。 初期条件は dp[0] = 1 (地面にいる状態が 1 通り) と dp[1] = 1 です。

遷移はフィボナッチと同じで、初期条件だけが違います。 実装は演習で書きます。

典型 2: 最小コスト

DP テーブルに入れる値は場合の数に限らず、「そこまでの最小コスト」も典型です。

高さの違う足場を 1 個先か 2 個先へ跳んで渡り、跳ぶたびに高さの差だけ体力を使います。 最後の足場までに使う体力の最小値を求めます。

let h = [2, 9, 4, 5, 1, 6, 7]
let n = h.count
var dp = [Int](repeating: 0, count: n)
dp[0] = 0
dp[1] = abs(h[1] - h[0])
for i in 2..<n {
    dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]),
                dp[i - 2] + abs(h[i] - h[i - 2]))
}
print(dp[n - 1])

遷移は、1 個前と 2 個前から跳ぶ場合の安い方を min で選ぶ式です。 場合の数なら和、最小化なら min と、目的に応じて遷移の形が変わります。

学びどころ

演習

1 行目に階段の段数 N (1 ≦ N ≦ 45) が入力されます。 1 歩で 1 段または 2 段上れるとき、地面 (0 段目) から N 段目までの上り方が何通りあるかを出力してください。

入力例:
10

出力例:
89

let n = Int(readLine()!)!
var dp = [Int](repeating: 0, count: max(n + 1, 2))
dp[0] = 1
dp[1] = 1
if n >= 2 {
    for i in 2...n {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
}
print(dp[n])