[leetcode] 70. Climbing Stairs

 

 

다이나믹 프로그래밍 문제 푸는 방법은 https://eyeballs.tistory.com/179 참고

 

길이가 n 인 계단을 오르는 방법의 수를 구하면 된다.

오르는 방법은 두 가지, 한 계단을 오르는 방법과 두 계단을 오르는 방법.

한 계단을 오르면 길이가 1 만큼 줄어들기 때문에, 길이가 n-1인 계단을 오르는 방법의 수를 구하면 된다.

두 계단을 오르면 길이가 2 만큼 줄어들기 때문에, 길이가 n-2인 계단을 오르는 방법의 수를 구하면 된다.

이 두 케이스를 합친 점화식은 d(n) = d(n-1) + d(n-2) 가 된다.

베이스 케이스는 간단하다.
계단이 하나뿐인 계단(d(1))을 오르는 방법은 1이고

계단이 두 개인 계단(d(2))을 오르는 방법은 2이다.

계단이 세 개인 계단(d(3))은 점화식으로 구할 수 있다.

 

 

class Solution:
    def climbStairs(self, n: int) -> int:
        d = dict()
        for i in range(1, n+1):
            if(i<3) : d[i]=i
            else : d[i] = d[i-1] + d[i-2]
        return d[n]

 

 

 

 

 

---

 

 

 

< English (feedback by ChatGPT) >

 

The task is to get how many steps we need to go upstair with the n length of the stair.

(The task is to find the number of ways to climb a staircase with n steps.)

 

There are two ways to go upstair, one step at once and two step at once.

(There are two possible moves: climbing one step at a time or two steps at a time.)

 

When go upstair with one step, length is decreased by 1, then we will get how many steps we need to go upstair with n-1 length of the stair.

(If you take one step, the remaining length becomes n-1, so the number of ways to climb is the same as for a staircase of length n-1.)

 

When go upstair with two steps, length is decreased by 2, then we will get how many steps we need to go upstair with n-2 length of the stair.

(If you take two steps, the remaining length becomes n-2, so the number of ways is the same as for a staircase of length n-2.)

 

The recurrence formula with the two cases is d(n) = d(n-1) + d(n-2)

(Combining these two cases gives the recurrence formula: d(n) = d(n-1) + d(n-2).)

 

The base case is simple.

(The base cases are simple:)

 

It's 1 way to go upstair with the 1 length of the stair.

(There is only 1 way to climb a staircase with 1 step,)

 

It's 2 ways to go upstair with the 2 length of the stair.

(and 2 ways to climb a staircase with 2 steps.)

 

The steps to go upstair with the 3 length of the stair could be calculated by the recurrence formula.

(For 3 steps, we can calculate the number of ways using the recurrence formula.)