【LeetCode】Climbing Stairs 解法【Python】

Climbing Stairs

leetcode.com

動的計画法のジャンルとして紹介されていたので解いてみたが、 なんとなく動的計画法ぽいなあと思いつつ具体的な解放が思いつかず。 ツリー構造で表現してみる。

これはn=3のとき。ノードの部分の残りの数が同じ場合は、その子は同じ構造になる。 最終的にエッジの数を数えればいい。 で、n=4のときは？最初の分岐で、1と2に分かれて、1の方は残り3になるので、n=3の構造と一緒。 そして2の方は残り2になるのでn=2と一緒。 これ、フィボナッチで表せそう。ということで解法。

コード

class Solution:
    def climbStairs(self, n: int) -> int:
        # 合計nになる1,2の組み合わせ
        # 0 = 1
        # 1 = 1
        # 2 = 2
        # 3 = 3
        # 4 = 5
        # 5 = 8
        # ※便宜上0 = 1とする
        ret = [1]*(n+1)
        for i in range(1,n):
            ret[i+1] = ret[i] + ret[i-1]

        return ret[n]    

実際にsolutionでフィボナッチの解き方が紹介されており、 自分の解法のような愚直なコードではなく、公式一発だった。

leetcode.com

また、動的計画法についてはこちら。

leetcode.com

i番目に到達できる経路を順次計算していく、という。自分のコードは結果的に動的計画法のやり方になっていた。