经典算法 求解台阶问题

求解台阶问题

题目描述

实现一个算法求解台阶问题。介绍如下：

对于高度为 n 的台阶，从下往上走，每一步的阶数为 1、2 或 3 中的一个。问要走到顶部一共有多少种走法。

---

输入描述

输入一个数字 N：

• 1 ≤ N ≤ 35
• 表示台阶的高度

---

输出描述

输出一行，为走法总数。

---

输入输出样例

输入

4

输出

7

---

c++代码

#include<bits/stdc++.h>using namespace std;int main() {int n;cin >> n;vector<int> dp(36);dp[0] = 1, dp[1] = 1, dp[2] = 2, dp[3] = 4;for (int i = 4; i <= 36; i++) dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];cout <<dp[n];return 0;
}//by wqs