题目来源：https://leetcode-cn.com/problems/climbing-stairs
题目假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
解题思路
- 其实本题可以分解为多个子问题，最优解则由子问题的最优解构建；
- 例如爬 i 阶楼梯，由两种方案：
- 爬上 (i-1) 阶，再爬 1 阶，到达 i 阶；
- 爬上 (i-2) 阶，再爬 2 阶，到达 i 阶；
- 由上面的情况，可得，要爬到 i 阶，即是到 (i-1) 和 (i-2) 的方法数总和；
- 用公式表示：dp[i] = dp[i-1] + dp[i-2]。
class Solution:
def climbStairs(self, n: int) -> int:
'''计算爬楼梯的方法数
Args:
n: 表示楼梯的台阶
Returns:
返回爬 n 阶楼梯的方法数
'''
# 如果台阶数 n 小于 2，直接返回 n
if n <= 2:
return n
# 将问题分解为多个子问题
# 爬 i 阶楼梯，可分解为爬 (i-1) 和 (i-2) 的方法总和
# 将列表索引定义为台阶数，n 为 0 时，这里直接给 None
# 只赋值给索引为 1，2 的两个元素
dp = [None, 1, 2]
for i in range(3, n+1):
dp.append(dp[i-1] + dp[i-2])
return dp[n]
斐波那契数
解题思路
- 根据上面动态规划得到的公式，dp[i] = dp[i-1] + dp[i-2] 可看出， dp[i] 就是第 i 个斐波那契数；
- 所以可得公式 Fib[i] = Fib[i-1] + Fib[i-2]；
- 现在的问题就是求第一项为 1，第二项为 2 的第 n 个斐波那契数，而 Fib[1] = 1，Fib[2]=2。
class Solution:
def climbStairs(self, n: int) -> int:
'''计算爬楼梯的方法数
Args:
n: 表示楼梯的台阶
Returns:
返回爬 n 阶楼梯的方法数
'''
# 如果台阶数 n 小于 2，直接返回 n
if n <= 2:
return n
# 将问题分解为多个子问题
# 爬 i 阶楼梯，可分解为爬 (i-1) 和 (i-2) 的方法总和
# 即是求第一项为 1，第二项为 2 的第 n 个斐波那契数
a, b = 1, 2
for _ in range(3, n+1):
a, b = b, b+a
return b
以上就是本篇的主要内容
题外话：越是恐慌，越是谣言四起。目前尽量不出门，照顾好自己，就是对社会最大的贡献。
