爬到第 x 级台阶的方案数是爬到第 x - 1 级台阶的方案数和爬到第 x - 2 级台阶的方案数的和。很好理解,因为每次只能爬 1 级或 2 级,所以 f(x) 只能从 f(x - 1) 和 f(x - 2) 转移过来,而这里要统计方案总数,我们就需要对这两项的贡献求和。
class Solution:
def climbStairs(self, n: int) -> int:
dp = [0] * (n+2)
#1阶台阶,只有一种方式(1)
dp[1] = 1
#2阶台阶,有两种方式(1+1, 2)
dp[2] = 2
#从第三个台阶开始遍历,第三个台阶,是第二个台阶的方法和第一个台阶的方法之和
#第四个台阶,是第三个台阶和第二个台阶方法之和,依此论推....
for i in range(3,n+1):
dp[i] = dp[i-1]+dp[i-2]
return dp[n]