70. Climbing Stairs

Problem Statement

link: https://leetcode.com/problems/climbing-stairs/description/ https://leetcode.cn/problems/climbing-stairs/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?

Example:

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

Solution Approach

The number of ways to reach each step is analogous to the Fibonacci sequence.

Algorithm

1. Initialize an array to track ways to reach each step.
2. Set base cases for the first two steps.
3. For each step, sum the ways of the two preceding steps.

Implement

    class Solution:
      def climbStairs(self, n: int) -> int:
        steps = [0] * (n + 1)
        steps[0], steps[1] = 1, 1
        for i in range(2, n + 1):
            steps[i] = steps[i - 1] + steps[i - 2]
        return steps[n]
 

    
    

Twitter  facebook  Email