LeetCode. Climbing Stairs [Dynamic Programming]

Problem:

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. 1 step + 1 step

2. 2 steps

 

Example 2:

Input: 3

Output: 3

Explanation: There are three ways to climb to the top.

1. 1 step + 1 step + 1 step

2. 1 step + 2 steps

3. 2 steps + 1 step

 

-Summary-

Bottom-up solution with Dynamic Programming

- Divide the problem into the small problems

if we see the number of the possible solution increase, it looks like below:

n         0 1 2 3 4 5

answer  0 1 2 3 5 8 

The above sequence is a Fibonacci series answer.

 

1. Create a base case.

2. Loop through and keep update the answer and previous 2 value.

 

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        
        if n == 2:
            return 2
        
        else:
            prev1 = 1
            prev2 = 2
            
            for i in range(3,n+1):
                cur = prev1+prev2
                prev1, prev2 = prev2, cur
                
            return cur

 

처음에는 계속해서 하나하나 possible case 만 바라보다가, 한참을 헤맸었다.

아래는 leetcode의 discussion에 있는 더 깔끔한 solution이다.

 

 

leetcode.com/problems/climbing-stairs/discuss/25313/Python-different-solutions-(bottom-up-top-down).

Python different solutions (bottom up, top down). - LeetCode Discuss

 

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]