You are climbing a stair case. It takes n steps to reach to 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: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps
Example 2:
Input: 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:
1 <= n <= 45
The description was taken from https://leetcode.com/problems/climbing-stairs/.
#O(N) Time, O(N) Space
class Solution:
def climbStairs(self, n: int) -> int:
if n is 0 or n is 1:
return n
dp = [0] * (n+1)
dp[1], dp[2] = 1, 2
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]From the problem description, we may notice that this problem is just implementing the Fibonacci formula up to the given, n.
However, that may be more of a coincidence than a solution. Like Decode Ways, Unique Paths, House Robber, Paint the Fence, this problem falls in the Dynamic Programming category of finding a running combination. To solve these problems, we will arrive at point B and look back at each potential point A that we got here from, and add the combinations from our point A's to point B.
We can handle the initial two test cases before we begin climbing any stairs.
If the input is zero, we have no staircase to climb, so we have zero combinations of getting there.
If the input is one, we can only take a one-step, so we will have a single combination of getting there.
if n is 0 or n is 1: return n
Now, let's initialize our dp cache.
A dp cache stores the answers for the subproblems given where the input equals the index, so the zeroth index stores the answer for if n was zero, index one stores the answer for if n was one, etc.
dp = [0] * (n+1)
We will now set our base cases, a crucial step for Dynamic Programming problems because this is us breaking down the overall problem into the smallest slivers of subproblems that we possibly can so that we may tabulate our overall solution by referencing these base cases.
If we were to have one step that we'd need to climb, then we could only do a one-step.
If we were to have two steps that we'd need to climb, then we could either do a one-step, or a two-step, totaling two possible combinations of getting there.
dp[1], dp[2] = 1, 2
Now, from the third step all the way to n, we would arrive at point B at the beginning of the iteration and we would just need to look at each possible point A we could have gotten here from.
In this case, we could have gotten here by taking a one-step from the stair directly behind us, or a two-step from the stair two behind us.
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
Once we have built up our cache, we can just return the nth index, as it will be the culmination of each subproblem before it.
return dp[n]
Since we are only referencing up to two indices behind us, that is actually all we need to keep track of, so we can improve this solution to a constant space solution.
What we will do instead is initialize our one-step and two-step variables accordingly, then we will iteratively increment the combinations of taking a one-step and two-step.
#O(N) Time, O(1) Spaceclass Solution: def climbStairs(self, n: int) -> int: if n is 0 or n is 1: return n one_step, two_step = 1, 2 for i in range(3, n+1): one_step, two_step = two_step, one_step + two_step return two_step