70. Climbing Stairs
https://leetcode.com/problems/climbing-stairs/
Easy
You are climbing a staircase. It takes n steps to reach 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: n = 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps
Example 2:
Input: n = 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
Problem
You’re climbing stairs. You can climb 1 or 2 steps at a time. How many distinct ways can you reach the top?
Approach
We use dynamic programming. Step 1 has 1 way, step 2 has 2 ways (1+1 or 2). Step 3 is the sum of step 1 and step 2. And so on — giving us our answer.
Source Code
func climbStairs(n int) int {
if (n == 0 || n == 1) {
return n
}
res := make([]int, n + 1)
res[1] = 1
res[2] = 2
for i := 3; i <= n; i++ {
res[i] = res[i - 1] + res[i - 2]
}
return res[n]
}
Closing
Do you have a better or simpler solution?
Feel free to leave a comment on my blog. Your feedback motivates me to keep writing. Thank you for reading, and let’s grow together to become better versions of ourselves.
