70. Climbing Stairs

This problem asks to find the number of distinct ways to climb n stairs, where you can climb either 1 or 2 steps at a time.

Approach 1: Dynamic Programming (Iterative)

This approach uses dynamic programming to efficiently calculate the number of ways to reach each stair. We create a DP array dp where dp[i] represents the number of ways to reach stair i.

• Base Cases: dp[0] = 1 (one way to reach the ground), dp[1] = 1 (one way to reach the first stair).
• Recursive Relation: To reach stair i, you can either come from stair i-1 (taking one step) or stair i-2 (taking two steps). Therefore, dp[i] = dp[i-1] + dp[i-2].

This iterative approach avoids redundant calculations, making it much more efficient than a purely recursive solution.

Time Complexity: O(n) - We iterate through the DP array once. Space Complexity: O(n) - We use a DP array of size n+1. This can be optimized to O(1) by only storing the last two values.

Code:

Python:

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

Java:

class Solution {
    public int climbStairs(int n) {
        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];
    }
}

C++:

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(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];
    }
};

Optimized Space Complexity (O(1))

We can further optimize the space complexity to O(1) by only storing the last two values in the DP array.

Python:

class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 1, 1
        for _ in range(2, n + 1):
            a, b = b, a + b
        return b

Java:

class Solution {
    public int climbStairs(int n) {
        int a = 1, b = 1;
        for (int i = 2; i <= n; i++) {
            int temp = a + b;
            a = b;
            b = temp;
        }
        return b;
    }
}

C++:

class Solution {
public:
    int climbStairs(int n) {
        int a = 1, b = 1;
        for (int i = 2; i <= n; ++i) {
            int temp = a + b;
            a = b;
            b = temp;
        }
        return b;
    }
};

Approach 2: Matrix Exponentiation

This approach leverages the fact that the sequence of the number of ways to climb stairs follows the Fibonacci sequence. We can use matrix exponentiation to calculate the nth Fibonacci number in logarithmic time. The core idea is to represent the Fibonacci recurrence relation as a matrix multiplication:

[[F(n), F(n-1)]] = [[1, 1], [1, 0]] * [[F(n-1), F(n-2)]]

By repeatedly squaring the matrix [[1, 1], [1, 0]], we can compute the nth Fibonacci number efficiently.

Time Complexity: O(log n) - Matrix exponentiation takes logarithmic time. Space Complexity: O(1) - Constant extra space is used.

Note: The code for this approach is more complex and involves matrix operations which are already provided in the original response. Implementing this efficiently requires either using a built-in matrix library or writing custom matrix multiplication and exponentiation functions. The code examples are shown in the initial response.

This detailed explanation provides a comprehensive understanding of the problem, different approaches, and their respective complexities. The choice of approach depends on the prioritization of time versus space complexity. For most cases, the optimized dynamic programming solution (O(1) space) offers the best balance.