動的計画法で2項間漸化式を解く

漸化式とは数列を再帰的に定める等式です。ある項とそれ以前の項の関係がはっきりしているなら、各項の値を求めることができます。

2項間漸化式を解く

a_1 = 6,a_(n) = a_(n – 1) – 8 によって定められる数列{an}の一般項を求めよ。

高校の数学の知識があれば自分で計算することもできるのですが(特性方程式を使う問題ですね)、ここはプログラミングで解を導きます。

求めたい項の最大値よりも1以上大きな配列を用意します。先頭は0、初項に相当するa[1]には初項を代入します。あとは第n項とn-1項の関係がわかっているので順番に値を代入していきます。

実行結果は以下のようになります。
6, 10, 22, 58, 166, 490, 1462, 4378, 13126, 39370,

3項間漸化式

3項間漸化式であっても同様に求めることができます。ここではフィボナッチ数列を求めることにします。

フィボナッチ数列は a[1] == 1, a[2] == 1, a[1] == 1, n ≧ 3)のときは a[n] = a_[n – 2] + a[n – 1] です。そこで求めたい項の最大値よりも1以上大きな配列を用意して、そこに値を代入していきます。

実行結果は 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, となります。

階段の上り方

動的計画法で解く問題として「階段の上り方」があります。一歩で階段を1段上るのと2段上るのを組み合わせて、n 段の階段を上る方法は何通りあるのかを考える問題です。実際問題としては一歩で上れるのは3段が限界だと思うのですが、プログラミングの世界ではなんでもありです。10段同時上りとか普通にあります。

1歩で1段と2段の組み合わせ方は?

階段を上るのに、1 歩で 1 段または 2 段を上ることができるとき、n 段の階段を上る方法は何通りあるでしょうか。

階段が0段であればなにもしないのでこの場合は方法が1通りあると考えます。1段なら1とおり、2段なら2とおりあります。もし階段が n – 1 段以下のとき答えが分かっているとすれば n段のときはそれらを利用して求めることができます。

n 段目に到達するには、n-1 段目から1段上る方法と、n-2 段目から2段上る方法の2つがあります。したがって n段のときの答えは n-1 段目に到達できる方法とn-2 段目に到達できる方法のふたつを足した数ということになります。dp[0] = 1、dp[1] = 1、 dp[n] = dp[n – 1] + dp[n – 2] の漸化式を解けば答えを求めることができます。

0段から10段まで何通りの上り方があるか表示させてみましょう。

1歩でa段とb段の組み合わせ方は?

では1歩で a 段または b 段を上ることができるとき、n 段の階段を上る方法は何通りあるでしょうか。この場合、解が存在しない場合があります。全部で5段ある場合、1歩で3段上がるのと4段上がる組み合わせでは解が存在しません。

では1歩で a 段、 b 段、または c 段を上ることができる場合も、ちょっと変更を加えるだけで解は得られます。

まとめ売りしているリンゴの買い方

りんごがまとめ売りをしています。必要な個数のリンゴを安く買うにはどのような組み合わせで買えばよいでしょうか?
ただし実際に買うりんごは 必要な個数を超えてもよいものとします。たとえば1個で150円、3個で250円、あわせて2個買うような場合は1個余分に買ってしまうことになりますが、3個で250円を買ったほうが安上がりです。

りんごのばら売りと2個のセット売り

八百屋でりんご1個が a 円で、りんご2個が b 円で売られています。このとき、n個のりんごを手に入れるために必要な金額の最小値はいくらでしょうか。

すでにn-1個のりんごを最も安く買うために必要な金額とn-2個のりんごを最も安く買うために必要な金額がわかっているとすれば、n-1 個のりんごを最も安く買ったうえで最後に1個のりんごを a 円で買う場合と、n-2 個のりんごを最も安く買ったうえで最後に2個のりんごを b 円で買う場合を考えて少ないほうが答えになることがわかります。

りんごの2個と5個のセット売り

次はりんご2個が a 円、5個が b 円で売られている場合を考えます。この場合、n 個のりんごを手に入れるために必要な金額の最小値はいくらでしょうか。実際に購入するりんごの個数は n を超えてもよいものとします。

前問では「1個と2個」だったものが「2個と5個」に変わりました。前問と同じ方法で以下のようなコードを書くとただしい解が得られません。これは3個のりんごをちょうど買う方法が存在しないからです。また4個買うより5個買うほうが安いという珍現象も発生しています。以下はまちがったやり方です。

実行結果

これだと正しい解を求めることができます。ただ面倒くさいです。

実行結果

上の書き方より下のように書いたほうがすっきりしているし、拡張性もあります。

以下のコードであれば「りんご x 個が a 円で、りんご y 個が b 円で売られています」という問題にも対応できます。