小明正在爬楼梯。楼梯总共有 n
级台阶,小明每次可以选择爬 1 级或 2 级台阶。请问小明爬到第 n
级台阶的不同方法有多少种。
注意:假设小明从地面(第 0 级台阶)开始爬楼梯,每次可以从当前台阶选择爬 1 级或 2 级台阶,直到到达第 n
级台阶。
输入一个整数 n
(1 ≤ n ≤ 40),表示楼梯的总级数。
输出一个整数,表示爬到第 n
级台阶的不同方法数。
2
2
3
3
动态规划(Dynamic Programming,简称 DP)是一种有效的算法设计思想,用于解决具有最优子结构和重叠子问题的复杂问题。其核心思想是通过记录已解决子问题的结果来避免重复计算,从而优化效率。关键在于定义问题的状态和状态转移方程。
以下是塔子哥通过集合视角一步步推导状态和转移方程的详细过程。
对于 (n = 4),所有可能的爬楼方式如下(5种):
0→1→2→3→4
0→1→2→4
0→1→3→4
0→2→3→4
0→2→4
将这些方案的集合定义为 D4,那么集合的大小 ∣D4∣=5 就是问题的答案。
考虑到达第 4 级楼梯的方式,可以从两种途径到达:
根据这两种情况,我们可以将集合D4分为两部分:
从集合划分可以观察到:
通过上述分析,可以得出递推关系:∣D4∣=∣D2∣+∣D3∣
我们可以用相同的思路分析任意 (n):要到达第 n 级楼梯,最后一步只能是从 n−1 或 n−2 到达。因此,所有从 0 到 n 的方案可以表示为:
∣Dn∣=∣Dn−1∣+∣Dn−2∣,这是爬楼梯问题的核心状态转移方程。
在动态规划中,需要明确边界条件来初始化状态转移:
从 (0) 到 (1) 的方案:只能 0→1,因此:∣D1∣=1
从 (0) 到 (2) 的方案:可以是 0→1→2或0→2,因此:∣D2∣=2
1.状态定义:
Dn:从第 (0) 级楼梯到第 (n) 级楼梯的所有方案数。
2.状态转移方程:
∣Dn∣=∣Dn−1∣+∣Dn−2∣
3.边界条件: ∣D1∣=1,∣D2∣=2
通过上述递推公式,可以高效地计算任意 (n) 的爬楼方案数。
n = int(input()) # 读取输入的整数n
dp = [0] * (n + 2) # 初始化动态规划数组,长度为n+2,防止下标越界
dp[1] = 1 # 第1个位置的值设为1
dp[2] = 2 # 第2个位置的值设为2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] # 当前位的值等于前两位的和
print(dp[n]) # 输出第n个位置的值