状态定义
设 dp(i)
表示到达第 i
级台阶的不同方法数,对应状态机的“节点”。
状态转移
要到达第 i
级,只可能从:
i-1
级再走 1 步;i-2
级再走 2 步。因此转移方程为:
dp(i)=dp(i−1)+dp(i−2)边界条件
dp(0)=1
:表示不走台阶也算一种方式。dp(1)=1
:只能一步到达第 1 级,只有 1 种方式。这样从 0
开始,按照状态转移“走”到 n
,累计所有路径数,就得到了最终答案。
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n; // 输入楼梯的级数
// D 数组,D[i] 表示到达第 i 级台阶的方法数
int D[n + 1];
// 初始化
D[1] = 1; // 第 1 级台阶的方法数为 1
D[2] = 2; // 第 2 级台阶的方法数为 2
// 递推
for (int i = 3; i <= n; i++) {
D[i] = D[i - 1] + D[i - 2]; // 根据递推公式
}
// 输出结果
cout << D[n] << endl;
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 读取输入的整数n
int[] dp = new int[n + 2]; // 初始化动态规划数组,长度为n+2,防止下标越界
dp[1] = 1; // 第1个位置的值设为1
dp[2] = 2; // 第2个位置的值设为2
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // 当前位的值等于前两位的和
}
System.out.println(dp[n]); // 输出第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个位置的值
小明正在爬楼梯。楼梯总共有 n
级台阶,小明每次可以选择爬 1 级或 2 级台阶。请问小明爬到第 n
级台阶的不同方法有多少种。
注意:假设小明从地面(第 0 级台阶)开始爬楼梯,每次可以从当前台阶选择爬 1 级或 2 级台阶,直到到达第 n
级台阶。
输入一个整数 n
(1 ≤ n ≤ 40),表示楼梯的总级数。
输出一个整数,表示爬到第 n
级台阶的不同方法数。
2
2
3
3