科目Bの動的計画法の問題の解き方｜表を小さい順に埋めて追う

dp[i − 1] と dp[i − 2] を足しているのは分かる。でも、なぜそれで答えになるのかが分からない。

科目Bの問題で、配列の前の値を使って次の値を決めていくコードを見て、手が止まったことはありませんか？

動的計画法という名前を聞くだけで、難しいアルゴリズムだと身構えてしまう人も多いのではないでしょうか。

大丈夫です。科目Bで出る動的計画法は、小さい問題の答えを表に書いておき、それを使って少し大きい問題の答えを出す、という手順のくり返しにすぎません。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務でも、同じ計算を何度もくり返して画面の表示が遅くなっていた処理を、一度求めた結果を配列に残す形に直して、数十倍速くしたことがあります。

そのとき役に立ったのは、難しい理論ではありませんでした。小さな入力で、表のどのマスがどのマスから決まるのかを紙に書き出したことが、修正の決め手になりました。

この記事では、動的計画法の問題を、科目Bの解き方に合わせて5つの段階で紹介します。科目B全体の中でこうした問題がどんな位置にあるのかを先に確かめたい人は、親記事から読んでおくと流れがつかみやすくなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

動的計画法の問題は何を聞いているのか¶

最初に、動的計画法とは何かを短く押さえておきましょう。名前は大げさですが、やっていることは、答えを表に書きためていくことです。

動的計画法とは、小さい問題の答えを配列に記録しておき、それを組み合わせて大きい問題の答えを求める方法のことです。一度求めた答えは配列に残っているので、同じ計算を二度する必要がありません。

身近な例で考えてみましょう。1段か2段ずつ階段を上るとき、6段目までの上り方は何通りあるでしょうか？

いきなり6段目を考えると混乱します。けれども、6段目に着く直前は、5段目か4段目のどちらかにいたはずです。

つまり、6段目までの上り方は、5段目までの上り方と4段目までの上り方を足した数になります。この考え方を1段目から順に表へ書いていくのが、動的計画法の基本形です。

科目Bで問われる形¶

試験の擬似言語で動的計画法が出るときは、考え方そのものより、表を埋める式やループの範囲が問われます。どんな形で聞かれやすいのかを、表に整理しました。

どの形でも、中心にあるのは、最初に入れる値と、表を埋める1行の式です。この2つを小さな例で確かめられれば、問われ方が変わっても同じ手順で解けます。

再帰で解く問題との違い¶

先ほどの階段の考え方は、再帰呼び出しでもそのまま書けます。6段目を求める関数が、5段目と4段目を求める関数を呼び出す形です。

ただし、再帰のまま書くと、4段目の答えを何度も計算し直すことになります。動的計画法は、その答えを配列に残しておき、2回目からは表を見るだけで済ませる方法だと考えると分かりやすくなります。

再帰呼び出しの追い方そのものに不安がある場合は、こちらの記事で先に整理しておくと読みやすくなります。

【関連記事】基本情報科目Bの再帰呼び出しがわからない人への対策方法を解説｜擬似言語で処理を追うコツ

まず目を付ける場所¶

動的計画法が何かつかめたら、次はコードのどこから読むかを決めます。動的計画法の問題では、目を付ける場所が3つあります。

ひとつ目は表の初期値、ふたつ目はループの開始位置と向き、みっつ目は表を埋める行の右辺です。この3か所が分かれば、ずれた選択肢をほぼ見抜けます。

初期値は何も計算しなくても分かるマス¶

最初に確かめたいのが、ループに入る前に代入されている値です。dp[1] ← 1 や dp[2] ← 2 のように、計算しなくても答えが分かる小さいマスが入っています。

階段なら、1段目までの上り方は1段上る1通りだけです。2段目までは、1段ずつ2回か、2段を1回かの2通りになります。

なぜ、わざわざ最初のマスだけ手で入れるのでしょうか？ 表を埋める式は前の2マスを使うので、前のマスが存在しない最初の部分だけは、式では決められないからです。

ループは小さい添字から大きい添字へ¶

次に見るのが、ループの範囲と向きです。動的計画法では、ほとんどの場合、i を小さいほうから大きいほうへ増やしていきます。

dp[i] を求めるには、dp[i − 1] と dp[i − 2] がすでに埋まっていなければなりません。だから、小さいマスから順に埋めていく必要があるわけです。

開始位置にも注意しましょう。初期値を dp[1] と dp[2] に入れたなら、ループは i が 3 から始まるのが自然です。2 から始めると、せっかく入れた dp[2] を上書きしてしまいます。

表を埋める行は前のどのマスを使うか¶

最後に見るのが、dp[i] ← dp[i − 1] ＋ dp[i − 2] のように、表を埋めている行です。この1行が、問題の考え方をそのまま式にしたものです。

右辺の dp[i − 1] は、1段手前からの上り方の数です。dp[i − 2] は、2段手前からの上り方の数です。

最後の一歩が1段か2段かで、上り方は重ならずに2つのグループに分かれます。だから、2つを足せばちょうど全部の上り方になります。

例題：階段の上り方を表で数える¶

ここからは、実際の例題で追い方を確かめます。この記事の例題は説明のために作成したもので、IPA の公開問題そのものではありません。

次のプログラムは、1段か2段ずつ階段を上るとき、n 段目までの上り方が何通りあるかを返す関数です。配列の添字は1から始まり、n は 2 以上とします。

○整数型: countWays(整数型: n)
  整数型の配列: dp ← {n個の 0}
  整数型: i
  dp[1] ← 1
  dp[2] ← 2
  for (i を 3 から n まで 1 ずつ増やす)
    dp[i] ← dp[i − 1] ＋ dp[i − 2]
  endfor
  return dp[n]

countWays は、最初に dp[1] と dp[2] へ答えを手で入れます。そのあと、3段目から順に、前の2マスを足して表を埋めていき、最後に dp[n] を返します。

では、countWays(6) の戻り値は何になるでしょうか？

トレース表で表を小さい順に埋める¶

頭の中だけで足し算を続けると、どのマスを足したのかが分からなくなりがちです。そこで、ループ1回ごとに、使う2つのマスと、書き込む位置と、その値をトレース表に書きます。

ポイントは、使うマスの列を2つに分けて、どちらも先に埋まっていることを確かめながら進めることです。こうしておくと、表が小さい順に埋まっていく様子が一目で分かります。

できあがった dp は {1, 2, 3, 5, 8, 13} です。return dp[n] で dp[6] を返すので、戻り値は 13 になります。

答えが合っているか不安なときは、小さいマスを直接数えて確かめましょう。3段目なら、1＋1＋1、1＋2、2＋1 の3通りで、表の dp[3] と一致しています。

トレース表の書き方そのものに慣れていない場合は、こちらの記事で基本から確認できます。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

一歩の種類が変わったら式も変わる¶

今度は、1段か3段ずつ上る場合を考えてみましょう。最後の一歩が1段なら i − 1 段目から、3段なら i − 3 段目から来たことになります。

そのため、表を埋める式は dp[i] ← dp[i − 1] ＋ dp[i − 3] に変わります。前の3マスまで見る必要があるので、初期値も dp[1] から dp[3] まで手で入れることになります。

ここで大切なのは、式を暗記することではありません。最後の一歩で何通りに分かれるかを考えれば、どのマスを足すのかは自然に決まります。

足すのではなく小さいほうを選ぶ形¶

動的計画法には、足し算ではなく、小さいほうを選ぶ形もあります。たとえば、各段に通行料がかかるとき、いちばん安く上る費用を求めるような問題です。

この場合、表を埋める行は dp[i] ← cost[i] ＋ min(dp[i − 1], dp[i − 2]) のような形になります。1段手前と2段手前のうち、安く来られたほうを選んで、その段の料金を足すという意味です。

式の形は変わっても、追い方は同じです。小さい順にマスを埋め、使う2マスがすでに決まっていることを表で確かめながら進めましょう。

間違いやすい選択肢の見分け方¶

動的計画法の問題では、初期値やループの範囲を少しだけずらした選択肢が並びます。どんな誤りが用意されやすいのかを知っておけば、選択肢を見た瞬間に候補を絞れます。

例題の countWays(6) を使って、よくある誤りを表にまとめました。

正解の 13 に対して、8 のように近い数字が選択肢に並ぶのがこの種の問題の特徴です。計算結果だけを見て選ぶと、うっかり近い数字に飛びついてしまいます。

小さい n で選択肢を試す¶

式で迷ったら、n を 3 や 4 のような小さい値にしてみてください。3段目までの上り方は、手で数えれば3通りだとすぐに分かります。

正しい式なら dp[3] は 2 ＋ 1 で 3 になり、手で数えた数と一致します。dp[i − 1] ＋ dp[i − 1] の形だと 2 ＋ 2 で 4 になってしまうので、すぐに誤りだと分かります。

小さい入力は、答えを手で確かめられる、いちばん信頼できる道具です。選択肢ごとに1回試すだけで、ずれた式をほとんど落とせます。

再帰版との違いは計算量で見る¶

動的計画法の問題では、同じ答えを返す再帰版のコードが比べられることもあります。どちらも正しく13を返すので、設問が何を問うているかを読み分けることが大切です。

設問が戻り値だけを聞いているなら、どちらの書き方でも答えは同じです。一方で、効率を聞いているなら、同じマスを何度も計算し直す再帰版より、表を1回ずつ埋める動的計画法のほうが速い、というのが答えになります。

例題の countWays は、ループが一重で、各マスを1回だけ計算します。ループの形から処理の速さを見積もる考え方は、こちらの記事で詳しく扱っています。

【関連記事】科目Bの計算量問題の解き方｜ループの形からオーダーを判断する

途中までの結果を配列にためておく発想は、累積和の問題とよく似ています。あわせて読んでおくと、表を埋める感覚がつかみやすくなります。

【関連記事】科目Bの累積和問題の解き方｜途中までの合計を配列にためて追う

Giji Academy のシミュレーターで動かす¶

紙のトレース表で動きをつかんだら、最後は実際に動かして確かめましょう。前のマスから次のマスが決まる処理ほど、動かして見る効果は大きくなります。

Giji Academy の擬似言語シミュレーターでは、擬似言語のコードを1行ずつ実行し、変数や配列の値が変わる様子を目で確かめられます。自分で書いたトレース表と見比べながら進めると、どの回で予想とずれたのかがすぐに分かります。

試すときは、まず正しい countWays を動かして、dp が {1, 2, 3, 5, 8, 13} になるのを確かめてください。そのあと、初期値を dp[2] ← 1 に書き換えて、表全体が1つずつ後ろにずれる様子を見ると、初期値の大切さが体で分かります。

慣れてきたら、一歩の種類を1段か3段に変えたり、n を大きくしたりしてみましょう。表のどのマスがどのマスから決まるのかが、少しずつ見えてくるはずです。

まずはGiji Academy の擬似言語シミュレーターで講座を選び、表が1行ごとに埋まっていく様子を確かめてみてください。

まとめ¶

科目Bの動的計画法の問題は、難しい理論を問うものではありません。小さいマスの答えを手で入れ、前のマスを使って表を小さい順に埋めていけば、落ち着いて解けます。

この記事でお伝えした5つの段階を振り返っておきましょう。

最初は、n が5前後の小さな例で十分です。何度か表を書くうちに、dp[i] ← dp[i − 1] ＋ dp[i − 2] を見ただけで、最後の一歩で場合を分けているのだと分かるようになります。

表は小さい順に埋める。答えに迷ったら小さい入力を手で数える。 この2つを習慣にしておけば、動的計画法の問題にも自信を持って向き合えます。次に前のマスを使うコードに出会ったら、まずは表の最初の2マスを書くところから始めてみてください。