[LeetCode] 70. Climbing Stairs (Easy/Python)

Climbing Stairs - LeetCode

Above is the link to the problem.

 

Problem

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

 

Example 

Input: n = 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

 

Analysis

There is only two way (1 step or 2 steps) when you start to climb the stair.

If n=3 and If you climb the first step, it can be expressed like below.

So, for climbing 3 steps, it is equal to the sum of climbing 1 step and 2 steps.

 

We can express this more generally.

Let X(n) = number of cases that climb n steps of the stairs. 

Above example X(3) = X(2) + X(1)

X(n) = X(n-1)+ X(n-2) when n>=3 in general

And this form is Fibonacci numbers.

in this case X(1) = 1, X(2) = 2

 

I solved this problem by writing the below code.

 

 

Updating the variable for the next loop.

Express X(n) = X(n-1) + X(n-2) as k = first_Before + second_Before

 

When n=1, result : (second_Before)0+(first_Before)1 = 1

When n=2, result : (second_Before)1+(first_Before)1 = 2

When n=3, result : (second_Before)1+(first_Before)2 = 3

...

 

This code gets the top 44.44% of time efficiency and the top 88.19% of space efficiency.