#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
int  dp[21];
dp[1]=1;
dp[2]=2;
dp[3]=4;
for(int i=4;i<=20;i++)
{
	dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
}
while(cin>>n){
	cout<<dp[n]<<endl;
	
}
}

• 初始化：

  • dp[1] = 1：爬到第1级台阶只有1种方法（走1步）。

  • dp[2] = 2：爬到第2级台阶有2种方法（1+1 或 直接走2步）。

  • dp[3] = 4：爬到第3级台阶有4种方法（1+1+1, 1+2, 2+1, 直接走3步）。

• 状态转移：

  • 对于第 i级台阶，可以从第 i-1 级走1步，或者从第 i-2级走2步，或者从第i-3级走3步。

  • 因此，。dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

• 返回值：返回 ，即爬到第 级台阶的方法数。dp[n]