LC70.md

Problem: Climbing Stairs

Difficulty: Easy

Description:

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?

Examples:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

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

Constraints:

1 <= n <= 45

Solutions:

For the DP approach we create an array of size n+1 and for all possible values from 1 to n we calculate the number of ways using 1 or 2. In the meantime, we store all the values and skip the double counting. The final element of the array will be the answer. The solution has time and space complexity of O(n).

def climbStairs(n):
    """
    :type n: int
    :rtype: int
    :Time Complexity: O(N)
    :Space Complexity: O(N)
    """
    climbs = [1, 2]
    dp = [0] * (n+1)
    dp[0] = 1

    for i in range(1, n+1):
        for c in climbs:
            if i - c >= 0:
                dp[i] += dp[i-c]

    return dp[-1]