Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0070 - Climbing Stairs
    0070 - Climbing Stairs
    0070 - Climbing Stairs
    0070 - Climbing Stairs

    0070 - Climbing Stairs

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/climbing-stairs/

    Solution 1 - Dynamic Programming (Bottom-Up)

    You are climbing a staircase that takes n steps to reach the top. Each time you can climb either 1 or 2 steps. Find the number of distinct ways to reach the top. This is equivalent to the Fibonacci sequence: the number of ways to reach step i is the sum of ways to reach step i-1 and step i-2. Build up the answer iteratively from the base cases.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)

    Solution 2 - Space-Optimized (Two Variables)

    Instead of storing the entire DP array, only track the previous two values. At each step, compute the current value as the sum of the two previous values and shift them forward. This reduces space to O(1).

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)
    """ 0070.1 - Climbing Stairs - Solution 1 - Dynamic Programming (Bottom-Up) """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def climbStairs(self, n: int) -> int:
        """Climbing Stairs Function"""
        if n <= 2:
            return n

        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2

        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]

        return dp[n]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().climbStairs(2))   # 2
    print(Solution().climbStairs(3))   # 3
    print(Solution().climbStairs(5))   # 8
    print(Solution().climbStairs(45))  # 1836311903


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0070.2 - Climbing Stairs - Solution 2 - Space-Optimized (Two Variables) """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def climbStairs(self, n: int) -> int:
        """Climbing Stairs Function"""
        if n <= 2:
            return n

        prev2 = 1
        prev1 = 2

        for i in range(3, n + 1):
            curr = prev1 + prev2
            prev2 = prev1
            prev1 = curr

        return prev1


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().climbStairs(2))   # 2
    print(Solution().climbStairs(3))   # 3
    print(Solution().climbStairs(5))   # 8
    print(Solution().climbStairs(45))  # 1836311903


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()