問題に挑戦してみよう！

実際にコードを書く問題にいくつか挑戦してみましょう。
ホワイトボートがない方は、紙とペンを用意してくださいね。

今回は、『Chapter 8 - 再帰と動的計画法』の問8.1から、次のような問題を紹介します。

すぐに「わかった！」という方は、実際にコードを書いてから続きを読んでください。そうでない方は、ゆっくりと進めてみましょう。

ヒントを活用する

実際の（書籍上の）問題には、問題文の後に

のようなヒント番号が書かれています。本書には付録として、問題についてのヒントがいくつ与えられています。番号が連続していないのは、1つ目のヒントを読んだ後、次のヒントが視界に入ってしまわないように配慮されているからです。この配慮で「読みたくないのに読んでしまった…！」ということがなくなります。

まずは、その中の1つ(#152)を見てみます。

このヒントを元に考えてみましょう。

最初のアプローチ

この問題を、次のように読み替えます。

n段目で上り終えるとき、一番最後のステップは3ステップ、2ステップ、1ステップのいずれかです。次のヒント(#178)を見てみましょう。

100段目に到達するのは、

・ 99段目まで進み、1段上がる。
・ 98段目まで進み、2段上がる。
・ 97段目まで進み、3段上がる。

場合のいずれかです。では、n段目で最後まで到達するには何通りの方法があるでしょうか？100段目の場合と同じようにn段目までのすべての経路について考えた場合、前の3つのステップごとに経路を分けて組み立てることができます。n段目に到達するのは、次のいずれかの方法です：

・（n-1）段目まで進み、1段上がる。
・（n-2）段目まで進み、2段上がる。
・（n-3）段目まで進み、3段上がる。

したがって、これらの経路の数を合計するだけで済みます。

経路の合計

経路を合計する場合、注意点はありそうですか？念のため、次のヒントを見ておきましょう。

普通に足すだけで良さそうですが、ついでにもう1つヒントを確認しておきます。

「99段目まで上がって、それから98段目まで上がって、それから97段目まで上がる」というのはおかしな話で、「99段目まで上がる、もしくは98段目まで上がる、もしくは97段目まで上がる」とそれぞれ独立に考えるべきですね。ですから足し合わせる方法で問題なさそうです。

最初のアルゴリズム

まずは計算効率を気にせず単純なアルゴリズムを考えてみましょう。
これまでの考え方に従うと、次のようなロジックになります：

	countWays(n-1) + countWays(n-2) + countWays(n-3)

1つ少しだけ複雑な点は、基底状態の定義です。階段の0段目にいる場合（階段上に立っている状態）、その段までの経路は0でしょうか、あるいは1でしょうか？
つまり、countWays(0) はいくつであるかということです。 1ですか？ それとも0ですか？

それはどちらでも定義することができます。「正しい」答えはありません。

しかし、1と定義する方がはるかに簡単です。0と定義した場合、追加の基底状態が必要になります（そうでなければ、延々と0が追加されることになります）。

では、実際にコードを書いてみましょう。
本書ではJavaで実装されていますので、今回はすべてJavaのコードで統一しておきます。

このアルゴリズムの実行時間は、3つの分岐を繰り返すためO(3ⁿ)となり、指数関数的になってしまいます。

ここで「O(文字式)」という表記が出てきました。これは、「ビッグ・オー記法」というアルゴリズムの性能を記述するために使う表記方法で、本書ではかなりのページ数を割いて説明されている重要な概念です。

実行時間が指数関数的に増加するアルゴリズムは、一般的には良いアルゴリズムと言えません。

このグラフの左から2番目が指数関数的な実行時間を表します。

最適化を行う

前述のcountWaysによる解法は、同じ引数で何度も呼び出されているということで、明らかに無駄ですね。これはメモ化（memoization）という手法を用いて改良できます。

基本的に、前に n の値を見たことがある場合はキャッシュされた値を返します。新しい値を計算するたびに、それをキャッシュに追加します。

通常、キャッシュにはハッシュマップ（Javaの場合は HashMap<Integer, Integer> ）を使用します。この場合、キーは1～nの範囲のみになります。ですので整数配列を使用する方がコンパクトです。

プラスアルファ

解法としてはこれで終わりですが、本書ではさらに次のようなことが書かれています。

面接官にこの問題を伝えるのはすばらしいことです。おそらくそれを回避するように言われることはないと思いますが（BigIntegerクラスではできますが）、これらの問題について考えることを実証するのは良いことです。

すぐにオーバーフローしてしまうとありますので、ここからは実際にコードを動かして確かめてみましょう。

import java.util.*;

class TripleStep
{
	public static void main (String[] args) throws java.lang.Exception
	{
		for(int i=1; i<40; ++i) {
			System.out.printf("%2d:%d\n", i,  countWays(i) );
		}
	}

	private static int countWays(int n) {
		int[] memo = new int[n + 1];
		Arrays.fill(memo, -1);
		return countWays(n, memo);
	}

	private static int countWays(int n, int[] memo) {
		if (n < 0) {
			return 0;
		} else if (n == 0) {
			return 1;
		} else if (memo[n] > -1) {
			return memo[n];
		} else {
			memo[n] = countWays(n - 1, memo) + countWays(n - 2, memo) +
			countWays(n - 3, memo);
			return memo[n];
		}
	}
}

クラス名を TripleStep としましたので「TripleStep.java」という名前で保存します。これをコンパイル・実行すると次のように表示されます。

$ javac Triplestep.java

$ java TripleStep
 1:1
 2:2
 3:4
 4:7
 5:13
 6:24
 7:44
 8:81
 9:149
10:274
11:504
12:927
13:1705
14:3136
15:5768
16:10609
17:19513
18:35890
19:66012
20:121415
21:223317
22:410744
23:755476
24:1389537
25:2555757
26:4700770
27:8646064
28:15902591
29:29249425
30:53798080
31:98950096
32:181997601
33:334745777
34:615693474
35:1132436852
36:2082876103
37:-463960867
38:-1543615208
39:75300028

確かに37のところで負の値になり、オーバーフローを起こしているように見えます。このような問題点を指摘しなかったとしてもマイナス評価になることはありませんが、指摘できていれば印象はより良くなる可能性があります。

最後に

今回は、比較的短めのコードになる問題を選んで紹介してみました。
次回はまた変わったタイプの問題を紹介する予定です。