< Back 70. Climbing Stairs We're given n, the number of steps in a staircase. We're aksed to find out how many different ways we can climb to the stop of the staircase given that we can take 1 or 2 steps during each move. Regular dynamic programming question. Thinking of this in terms of states, we have two choices to make during each move, 1 step or 2 steps. And we know the previous decisions compound into the current decision. Instead of recomputing the number of ways we've could've reached our current state, we should just reuse previously calculated solutions. If n is 1 or 2, we just return each value, respectively. Otherwise, we initialize a table of length n to memoize our answers. We set the first two values to 1 and 2, respectively. Then, we iterate from 2 to n, calculating the number of ways to reach the current state by adding the number of ways to reach T[i - 1] and T[i - 2]. Once we're done, T[n - 1], the top of the staircase, will contain the number of ways to reach the top of the staircase. The solution is as follows: class Solution: def climbStairs(self, n: int) -> int: if n == 1: return 1 if n == 2: return 2 T = [0] * n T[0] = 1 T[1] = 2 for i in range(2, n): T[i] = T[i - 1] + T[i - 2] return T[n - 1] _ Time Complexity: O(n) - Where n is the input, n, we iterate from 2 to n to calculate the number of ways to reach the top of the staircase. _ Space Complexity: O(n) - We maintain a table of length n to memoize our answers.