AcWing 3643. 上楼梯
原题链接
简单
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
//题解
int climbStairs(int n) {
if(n < 3) return n; //n为1或2的情况
vector<int> dp(n + 1);
//初始化dp数组
dp[1] = 1; //第0级台阶走到第1级台阶共有1种方法
dp[2] = 2; //第0级台阶走到第2级台阶共有2种方法
dp[3] = 4; //第0级台阶走到第3级台阶共有4种方法
for(int i = 4;i <= n;i++) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; //dp数组的递推公式
}
return dp[n]; //第0级台阶走到第n级台阶共有dp[n]种方法
}
};
void func() {
int n;
Solution st;
cin >> n;
int ans = st.climbStairs(n);
cout << ans;
}
int main() {
func();
return 0;
}