algoadvance

Leetcode 70. Climbing Stairs Sure, let’s go through the problem “70. Climbing Stairs” on LeetCode.

Problem Statement:

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 1:

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

Example 2:

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:

Clarifying Questions:

  1. Can n be 0? (No, the minimum value for n is 1 according to the constraints.)
  2. Are there any specific restrictions or edge cases that we should be aware of other than those mentioned? (No additional constraints beyond those provided.)

Strategy:

This problem can be solved using Dynamic Programming.

  1. Base Cases:
    • If n is 1, there is only 1 way to get to the top (1 step).
    • If n is 2, there are 2 ways to get to the top (1 step + 1 step, 2 steps).
  2. Recurrence Relation: For n steps, the number of ways to get to the top can be thought of as:
    • From the last step, you could have come from n-1 or n-2 steps.
    • Therefore, the number of ways to get to step n is the sum of the number of ways to get to step n-1 and step n-2.

    Mathematically, this can be written as: [ \text{ways}(n) = \text{ways}(n-1) + \text{ways}(n-2) ]

  3. We can use an array to store the number of ways to reach each step up to n.

Code:

#include <iostream>
#include <vector>

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;

        std::vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
};

int main() {
    Solution solution;
    std::cout << solution.climbStairs(2) << std::endl; // Output: 2
    std::cout << solution.climbStairs(3) << std::endl; // Output: 3
    std::cout << solution.climbStairs(4) << std::endl; // Output: 5
    return 0;
}

Time and Space Complexity:

This approach ensures that our solution is both efficient and easy to understand.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI