[일일 1문제 leetcode] 70 Climbing Stairs

이 문제는 시간이 오래 걸렸고 DP를 처음 접하기 시작했기 때문에 사고 훈련이 좀 더 필요하다.제목: **You are climbing a stair case.It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?** Note: Given n will be a positive integer.

Example 1: Input: 2 Output: 2 Explanation: There are two ways to climb to the top.

1 step + 1 step

2 steps

Example 2: Input: 3 Output: 3 Explanation: There are three ways to climb to the top.

1 step + 1 step + 1 step

1 step + 2 steps

2 steps + 1 step

본 주제의 Solution은 매우 상세한 분석 설명을 제공하므로 아래에서 제공한 주소를 참고할 수 있습니다.여기서 DP 방법을 사용하여 문제를 하위 문제로 분해합니다.상태 정의: ii는 사다리의 ii층을 나타내고 ii층에 도달하는 상태는 두 가지 방법이 있다.

상태 i -3 1 i -3 1에서 한 걸음

상태 i -3 2 i -3 2에서 2보 도착

f[i] f[i]는 ii층까지의 모든 방법을 나타냅니다.
상태 이동 방정식: f[i]=f[i-3-1]+f[i-3-2] f[i] = f[i-3-1] + f[i-32]
너는 이 방정식이 매우 낯익다고 느낄 것이다. 그것이 바로 유명한 피보나치 수열 표현식이다. 단지 조건 i>=2i>=2를 추가하기만 하면 된다.단지 이 제목에서 시작된 두 수는 [1,2][1,2]이지 [1,1][1,1]이 아니다.
코드는 다음과 같습니다.

class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """

        if n == 0 or n==1 or n==2:
            return n

        # f[i] = f[i-1] + f[i-2] ; f[1]=1,f[2]=2
        f = list(range(n+1))
        f[1]=1
        f[2]=2
        for i in range(3,n+1):
            f[i] = f[i-1] + f[i-2]


        return f[n]

참조 링크: 동적 계획에 대한 답변을 알고 있는 Letcode Solution