Climbing Stairs

https://leetcode.com/problems/climbing-stairs/

n = 5

                0
            ／　    ＼
        1             　2
       ／＼          　／＼
    2         3     　3    4
   ／＼      ／＼  　／＼ 　／＼
 3     4    4   5 　4   5 5   6

／＼ ／＼ ／＼　　 ／＼ 4 5 5 6 5 6　 5 6 ／＼ 5 6

n が 5 steps の場合、 8通りの選択が出来る。

DFS でも出来るかが 2^n となる。

そのため Dynamic Programming を使う。

同じ計算をする値は memoize する

| 8 | 5 | 3 | 2 | 1 | 1 | n に辿り着くまでの数

0 1 2 3 4 5(step) one two

n に辿り着くまでの数はBase Number を基に計算できる。

Time complexity: O(n) Mem complexity: O(n)

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        one, two = 1, 1
        
        for i in n:
            temp = one
            one = one + two
            two = temp
        return one