描述
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?
Subscribe to see which companies asked this question
分析
典型的动态规划题目,一句话说明动态规划这类题目的特点:某个状态总是依赖于前面1个或2个甚至多个状态,可能是前2个状态求最大值,也可能是求和,而边界状态是已知的。比如这题,如果是1阶的楼梯,有1种方式,2阶的楼梯,有2种方式,走到第n阶楼梯,可能是从n-1阶来的,也可能是从n-2阶来的,因此走第n阶可能的方式总数等于走n-1阶的方式总数加走n-2阶的方式总数。
解决方案1(python)
1 | class Solution: |
解决方案2(C++)
1 | class Solution { |
解决方案3(Golang)
1 | func climbStairs(n int) int { |