「問題解決力を鍛える!アルゴリズムとデータ構造」とLeetCodeで学ぶ再帰と動的計画法(メモ化)
再帰とメモ化 問題 再帰とメモ化 問題解決力を鍛える!アルゴリズムとデータ構造 というアルゴリズムとデータ構造を学ぶのに良い本があります。 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 =