再帰とメモ化

問題解決力を鍛える!アルゴリズムとデータ構造
というアルゴリズムとデータ構造を学ぶのに良い本があります。

LeetCodeの問題を解いていた時に、この本の中で解説されていた例とすごく被っている内容があったので、記事にしてみようと思いました。

問題

1137. N-th Tribonacci Number

難易度はEasy。
再帰の入門にうってつけです。

問題解決力を鍛える!アルゴリズムとデータ構造の4章の解説にもある通り、再帰関数のテンプレートは

(戻り値の型) func(引数){
	if(ベースケース){
		return ベースケースに対する値;
	}
	func(次の引数)
	return 答え
}

問題解決力を鍛える!アルゴリズムとデータ構造第4章設計技法(2):再帰と分割統治法

といったものです。

今回解く問題は、

トリボナッチ数列Tnは次のように定義される。

T0 = 0, T1 = 1, T2 = 1, そして n >= 0 で Tn+3 = Tn + Tn+1 + Tn+2 となる。

nが与えられたとき、Tnの値を返す。

という内容です。

では、こちらをPythonでかつ再帰で解いてみましょう。

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        elif n == 1 or n == 2:
            return 1
        return self.tribonacci(n-1) + self.tribonacci(n-2) + self.tribonacci(n-3)
# Time Limit Exceeded

しかし、これだとnが 30の時に時間切れとなり、正解とは認められません。

これは再帰で同じ処理が重複し、関数の呼び出し回数がとてつもない回数になっているためです。

ではこれを解決してみましょう。

class Solution:
    def tribonacci(self, n: int) -> int:
        memo = collections.defaultdict(int)
        memo[0], memo[1], memo[2] = 0,1,1
        for i in range(3,n+1):
            memo[i] = memo[i-1] + memo[i-2] + memo[i-3]
        return memo[n]
# Runtime: 28 ms, faster than 80.87% of Python3 online submissions for N-th Tribonacci Number.
# Memory Usage: 14.3 MB, less than 13.79% of Python3 online submissions for N-th Tribonacci Number.

この解法では一度計算したものをmemoという変数に保存し、仮に計算済みであれば関数を呼び出すのではなく値を直接返すようにしています。これをキャッシュといい、高速化するための手法です。

どうでしょうか。

これ以外にも問題を解決するための思考法などが満載の素晴らしい本なので、問題解決力を鍛える!アルゴリズムとデータ構造を買って実際に勉強されてみるといいかと思います。

今回はここまで。お疲れ様でした。