题目描述
现一个算法求解台阶问题。介绍如下：
- 对于高度为 nn 的台阶，从下往上走，每一步的阶数为 1，2，3 中的一个。问要走到顶部一共有多少种走法。
输入描述
输入一个数字 N (1≤N≤35)N (1≤N≤35)，表示台阶的高度。
输出描述
输出一行，为走法总数。
输入输出样例
输入
4
输出
7
解题思路
一、最核心的底层逻辑（全部看懂靠这个）
动态规划永远只思考 最后一步
DP万能思维：
&到达第 n 级台阶的所有方法 = 所有能一步走到 n 的位置的方案总和
本题规则：最后一步只能是三种情况
1. 最后走1步 → 说明我之前站在 n-1
2. 最后走2步 → 说明我之前站在 n-2
3. 最后走3步 → 说明我之前站在 n-3
所以公式直接推导出来：
dp[n] = dp[n-1] + dp[n-2] + dp[n-3]
二、手动枚举，彻底搞懂初始值
n = 1
只有 1 种：
1 → dp[1] = 1
n = 2
两种走法：
1+1 -> 2 dp[2] = 2
n = 3（重点，为什么是4，彻底讲透）
全部列出来：
1. 1 + 1 + 1
2. 1 + 2
3. 2 + 1
4. 3
一共 4种 -> dp[3] = 4
关键理解：
1+2 和 2+1 顺序不一样，是两种完全不同的走路方式，不能合并
三、完整解题思路总结
1. dp[i] 定义：走到第 i 级台阶的总方案数
2. 最后一步只有 1、2、3步三种可能
3. 递推式： dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
4. 初始化前3项：1、2、4
5. 循环从4推到n
6. 结果较大，必须用 long long 防溢出
完整代码
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int n;
long long dp[100];
scanf("%d",&n);
dp[1]=1;//从0到1,一步
dp[2]=2;//(1)从1到2 (2)从0到2
dp[3]=4;//(1)走一步:1+1+1 (2)1+2 (3)2+1 (4) 3步到
int i;
for(i=4;i<=n;i++)
{
dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
}
printf("%lld\n",dp[n]);
return 0;
}
踩坑记录
1. 最大误区：认为 n=3 是3种
忽略顺序不同算不同方案，1+2 和 2+1 是两种走法，所以是4种。
2. 容易和普通爬楼梯混淆
普通只能走1、2步： dp[i] = dp[i-1] + dp[i-2] ，本题能走3步，必须多加一项 dp[i-3]
3. 数据溢出问题
n到30+之后数字非常大，int存不下，必须用 long long
4. DP本质理解误区
DP不是暴力枚举所有路线
是利用前面算好的结果，累加最后一步的所有可能性。
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/2402_87421821/article/details/169950759
