leetcode easy 70 climbing stairs

こんにちは

今回の学びは

・ソートされた配列と二分木はよく似てるよ。

・できれば二分木探索を配列で実装していて 🙂

問題は。。。

まずは入出力をしっかりおさえましょう。

nが数字で与えられます。それが階段の数です

一回の選択として1か2のどちらかが選べて1は一歩、2は二歩勧めます。

頂上までいくまで何通りありますか？という問題

考えましょう

現時点の数を覚えておき(変数cur)　その時点でcurが最終ステップかどうか確認する、そうであればok

それよりも小さければ、続ける。それ以上であれば終了する。小さい場合はその時点からの動作は一歩か二歩

を選んで繰り返す。

簡単そうなのでササッと書いて提出すると、時間超過でエラーとなる。。。

class Solution:
    def rec(self, cur, n):
        if cur == n:
            return 1
        elif cur > n:
            return 0
        else:
            return self.rec(cur+1, n) + self.rec(cur+2, n)

    def climbStairs(self, n: int) -> int:
        return self.rec(0, n)

これわっ！！！　timespace analysisをやってないからこんことになるのだ！！！

ちゃんとtimespace analysisを実装まえにやりましょう

毎回2個の選択があるのでO(n**2)ということか。。。ではキャッシュしてどうか。

やってみます。

leetcode hard binary tree max path sumの問題でも似たような再帰があったのですが、これはキャッシュできない、そしてdfsのような操作パスなのが大きな違いですね。

okということでキャッシュしていきましょう

実装前後でこれは毎回書きましょう。timespace anaylysis (時間とスペースの分析）は　O(N**2) - CACHE

pseudocode（擬似コード）をかいてみますか。

。。。

実際の実装はこちら

from collections import defaultdict
class Solution:
    def __init__(self):
        self.cache = defaultdict(int)

    def rec(self, cur, n):
        if cur in self.cache: return self.cache[cur]
        if cur == n:
            self.cache[cur] = 2
            return 1
        elif cur > n:
            return 0
        else:
            step1 = self.rec(cur+1, n)
            self.cache[cur+1] = step1
            step2 = self.rec(cur+2, n)
            self.cache[cur+2] = step2
            return step1 + step2

    @timeit
    def climbStairs(self, n: int) -> int:
        self.cache = defaultdict(int)
        return self.rec(0, n)

実装後です。timespace anaylysis (時間とスペースの分析）は　実質O(n)くらいかとおもいます。なぜならほとんど全部キャッシュにあたるので。

なぜキャッシュにあたるのかはちゃんと説明できるようになりたいですね。

速かったので、嬉しい

まとめ

以上です