🗺️ アルゴリズムクエスト
STAGE 8 ― 再帰と動的計画法 ―
クリア 0 / 9
🧭 地図
STAGE 8

再帰と動的計画法

同じ計算を二度しない
🎯 ミッション
素朴な再帰が遅くなる理由と、動的計画法(表に書いて使い回す)で速くなる理由を説明できるようになろう。10段までの表を埋め、確認クイズに全問正解すれば合格。
未達成
ねこ博士
宝箱のある塔の階段は10段。1回に1段か2段ずつ上れるとき、上り方は何通りあるか。小さい段数で数えてごらん。
うさ美
1段なら「1」の1通り。2段なら「1+1」と「2」の2通り。3段なら「1+1+1」「1+2」「2+1」の3通り。
ねこ博士
一つ一つ数えると大変になるので、考え方を変えよう。n 段目に着く直前、最後の1回は何段上った?
うさ美
1段か2段のどちらかです。最後に1段上ったなら、その前は n−1 段目にいた。2段なら n−2 段目にいた。……だから、n 段目への上り方は、n−1 段目への上り方と、n−2 段目への上り方の合計。
ways(n) = ways(n−1) + ways(n−2) (ways(0) = 1、ways(1) = 1 とする) ways(2) = 1+1 = 2、ways(3) = 2+1 = 3、ways(4) = 3+2 = 5 ……
ねこ博士
大きな問題の答えを、同じ形の小さな問題の答えで書けた。この式は、プログラムにそのまま書ける。関数 ways が、自分自身を呼ぶんだ。
ways(n) = n が 0 か 1 なら 1、そうでなければ ways(n−1) + ways(n−2)
ねこ博士
関数が自分自身を呼ぶことを再帰と呼ぶ。クイックソートで、左右のグループに同じやり方を使ったのも再帰だった。大事なのは、「n が 0 か 1 なら 1」のように、もう自分を呼ばずに答えが決まる場合(終わりの条件)を必ず書くことだ。これが無いと、関数は永遠に自分を呼び続けて、スタックがあふれてしまう。
うさ美
きれいに書けました。これで10段を計算すると、どうなるんですか?
ねこ博士
ways(5) の呼び出しを、木の形に書いてみよう。ways(5) は ways(4) と ways(3) を呼ぶ。ways(4) は ways(3) と ways(2) を呼ぶ……。
うさ美
ways(3) が、ways(5) から直接1回と、ways(4) の中から1回、2回計算されている。ways(2) はもっと多い……。同じ計算を何度もやり直しています。
ねこ博士
そう。呼び出しの回数を数えると、n が1増えるごとに、だいたい1.6倍ずつ増えていく。n が 40 なら3億回を超える。同じ答えを何度も計算し直しているのが原因だ。
うさ美
一度計算した答えを、どこかに書いておけばいいのでは。
ねこ博士
それが動的計画法(DP)の考え方だ。小さい問題の答えを表に書いておいて使い回す。表を、小さい段から順に埋めていけば、どのマスも、すでに書いてある2つのマスを足すだけで決まる。
素朴な再帰:同じ小問題を何度も計算する。呼び出し回数は n とともに指数的に増える(O(1.6ⁿ) くらい) 動的計画法:小さい順に表を埋め、1マス1回の足し算 → O(n) メモ化:再帰の形のまま、一度計算した答えを表に書いて、次からはそれを返す。同じく O(n)
うさ美
書き方は同じ再帰でも、表があるかないかで、3億回と40回の違いになるんですね。
ねこ博士
そう。動的計画法が使えるのは、2つの条件がそろったときだ。「大きな問題の答えが、小さな問題の答えから作れる」こと、そして「同じ小さな問題が何度も出てくる」こと。カーナビの経路、文章の似ている度合い、限られた予算での最善の買い物など、多くの問題がこの形をしている。STAGE7 のダイクストラ法も、「確定した町の最短距離」を表に書いて使い回していたね。

確認クイズ

Q1. 階段の上り方 ways(n) = ways(n−1) + ways(n−2) が成り立つ理由は?

Q2. 素朴な再帰で ways(40) を計算すると、とても遅い理由は?

Q3. 再帰の関数に必ず書かなければいけないのは?