Leetcode 70. Climbing Stairs (Python)

Related Topic

Dynamic-Programming.

Description

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?

Sample I/O

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

Note:

Given n will be a positive integer.

Methodology

This question solved by Dynamic Programming.

1. Find the base case
   1. When climb 1 stair, we need 1 step
   2. when climb 2 stairs, we need 2 steps which 1+1 or 2
   3. when climb 3 stairs, we need 3 steps which 1+1+1, 1+2, 2+1
   4. when climb 4 stairs, we need 5 steps which 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 …. The base case will be:

      dp[1]=1,
      dp[2]=2,
      dp[3]=3,
      dp[4]=5
      .
      .
      .
      

2. Find the pattern:

   To reach the current stairs for example (stair 4), we can easily add 1 step from last stair (stair 3) and that will give us 1+1+1+1, 1+2+1, 2+1+1. Or we can easily add 2 steps from the one before last stair (stair 2) and that will give us 1+1+2 and 2+2. Since we can only move 1 or 2 steps each time. We do not need more previous stairs. So we get answer 5 in total.

3. Extended option:

   If we can move 1, 2 and 3 steps each time. we only need to add up total ways of last 3 stairs together.

Conditions

• If stair is 0, we will need 1 step to reach that, I guess this is because, no matter what, you have to pick up 1 or 2 steps. So dp[0] = 1

Code

def climbStairs(self, n: int) -> int:
        if n<=2: return n
        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]

BigO

We iterate all dp array, it will cost O(n), each value will add up last two value as result, it will cost (1+2), in total will be O(n+2n) and It is O(n)