70. Climbing Stairs - python3

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

뭔가 트리를 어떻게 해보면 될거같고
규칙이 있을것만 같고 그런데...(1, 2, 3, 5, 8, 13, ... 순으로 증가)
아무리 생각해도 내 머리로는 안돼서^^ 동지들의 도움을 받음

Other Answer 1:

class Solution:
    def climbStairs(self, n: int) -> int:
        if (n==1):
            return 1
        
        first = 1
        second = 2
        
        for i in range(3, n+1):
            third = first + second
            first = second
            second = third
        return second

피보나치 수열을 이용한 것

내가 찾던 규칙이 바로 이거였음

(0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 순으로 증가

규칙 찾겠다고 직접 계산할 때 input = 2 가 2 라서 피보나치인걸 눈치 못챈듯...

Other Answer 2:

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 0 or n == 1 or n == 2:
            return n
        s1 = 1
        s2 = 2
        for i in range(2,n):
                s2 += s1
                s1 = s2 - s1
        return s2

사실 이해 안감..

피보나치를 보고나니 대충 이해가 된다

n = 3 부터는 피보나치 수열대로 진행

Other Answer 3:

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        dp = [0]*(n+1)
        dp[1] = 1
        dp[2] = 2

        for i in range(3,n+1):
            dp[i] = dp[i-1] + dp[i-2]

        return dp[n]

DP 를 많이 이용하는 것 같은데.. 이거도 뭔지 잘 모르겠음

이것도 역시 피보나치를 보고나니 대충 이해가 된다

dp = [0]*(n+1) => n+1 크기의 배열이라는 의미인듯
나머지는 피보나치와 동일