[4코3파] #306. Leetcode 1-D Dynamic Programming (1)

[4코3파] 1명의 스위프트 개발자가 도망가고 4명의 코틀린 개발자, 3명의 파이썬 개발자의 코딩 테스트 스터디 : 4코3파

START :

[3코1파] 2023.01.04~ (306일차)
[4코1파] 2023.01.13~ (298일차)
[4코3파] 2023.10.01 ~ (36일차)

Today :

2023.11.05 [306일차]

Leetcode 1-D Dynamic Programming

[1] 70. Climbing Stairs

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

문제 설명

계단을 오를 때 각 단계마다 1단계 또는 2단계씩 올라가는 방법의 수를 찾는 문제이다. 주어진 계단의 수가 n이 주어지면, n개의 계단을 오를 때 가능한 방법의 수를 반환한다.

문제 풀이 방법

다이나믹 프로그래밍(Dynamic Programming)을 사용하여 n개의 계단을 오를 때 가능한 방법의 수를 f(n)이라고 정의한다.
f(n)을 구하기 위해서는 두 가지 경우를 고려한다.
n-1개의 계단을 올라온 후에 1단계를 더 오른 경우: f(n-1)
n-2개의 계단을 올라온 후에 2단계를 더 오른 경우: f(n-2)
따라서 f(n) = f(n-1) + f(n-2)가 된다.

초기 상태 설정:
n = 1일 때, 계단을 하나만 오를 방법은 1가지로, f(1) = 1.
n = 2일 때, 계단을 두 단계로 오를 방법은 2가지로, f(2) = 2.
다이나믹 프로그래밍으로 f(n) 계산:
초기 상태를 설정한 후, f(3)부터 f(n)까지를 순차적으로 계산한다.
각 단계에서 f(i)를 계산할 때, 이전의 f(i-1)과 f(i-2)를 사용하여 계산한다.
f(n)을 계산하면 n개의 계단을 오를 때 가능한 방법의 수가 된다.

내 코드

 class Solution:
    def climbStairs(self, n: int) -> int:
        tmp = [0,1,2]

        if n < len(tmp):
            return tmp[n]

        for i in range(3, n+1):
            step = tmp[i-2] + tmp[i-1]
            tmp.append(step)

        return tmp[n]  
            

---

여담

DP다 큰일이다