This is the "Climbing Stairs" problem from leetcode.com:
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?
Note: Given \$n\$ will be a positive integer.
Input: 2 Output: 2 Explanation: There are two ways to climb to the top.
- 1 step + 1 step
- 2 steps
Input: 3 Output: 3 Explanation: There are three ways to climb to the top.
- 1 step + 1 step + 1 step
- 1 step + 2 steps
- 2 steps + 1 step
I thought this question is very similar to Fibonacci question. I use dynamic programming,
dp[n] = dp[n - 1] + dp[n - 2] class Solution: # @param n, an integer # @return an integer def climbStairs(self, n): dp = [1 for i in range(n+1)] for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n]