LeetCode 70: Climbing Stairs Solution

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We can define a DP array where dp[i] represents the number of distinct ways to reach step i. We can then build up this array iteratively by considering the number of ways to reach the current step based on the number of ways to reach the previous two steps.

Initialize a DP array of size n+1 to store the number of ways to reach each step.
Set dp[0] = 1 and dp[1] = 1 as there is only 1 way to reach the first and second steps.
Iterate from i = 2 up to n and calculate dp[i] based on the sum of dp[i-1] and dp[i-2], as you can climb either 1 or 2 steps at a time.
Return dp[n] as the final answer.

Time Complexity: O(n)
Space Complexity: O(n)

Solution Code

class Solution {
    public int climbStairs(int n) {
        if (n <= 1) {
            return 1;
        }
        
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
}

Frequently Asked Questions

How to solve LeetCode 70 (Climbing Stairs)?

This page provides optimized solutions for LeetCode problem 70 (Climbing Stairs) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 70 (Climbing Stairs)?

The time complexity for LeetCode 70 (Climbing Stairs) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 70 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 70 in Java, C++, or Python.