EasyLeetCode #70Dynamic Programming

Climbing Stairs

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?

Constraints

1 <= n <= 45

Examples

Input: n = 3

Output: 3

1+1+1, 1+2, 2+1

Solution

Approach

DP where dp[i] = dp[i-1] + dp[i-2]. Ways to reach step i = ways from step i-1 (1 step) + ways from step i-2 (2 steps). This is Fibonacci.

def climbStairs(n):
    if n <= 2:
        return n
    prev, curr = 1, 2
    for _ in range(3, n + 1):
        prev, curr = curr, prev + curr
    return curr

Complexity

Time:O(n)

Space:O(1)

Hints

1.Think about the last step: 1 or 2
2.Relate f(n) to f(n-1) and f(n-2)
3.This is Fibonacci sequence

Asked at

Google