题目70：爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入：2输出：2解释：有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶
输入：3输出：3解释：有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶
于是有：
dp[i]表示爬到第i阶有多少方法dp[1] = 1; // i = 1dp[2] = 2; // i = 2dp[i] = dp[i-1] + dp[i-2]; // i >=3
class Solution {public:int climbStairs(int n) {if (n < 3) return n;vector<int> dp(n+1, 0);// dp[i]表示爬到第i阶有多少方法dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; ++i) {dp[i] = dp[i-1] + dp[i-2];}return dp[n];}};
示例1：
输入：n = 3输出：4说明: 有四种走法
输入：n = 5输出：13
n范围在[1, 1000000]之间
分析
dp的经典且最简单的问题，可以参见上一篇爬楼梯问题，但这里有点小细节需要注意
三个数的和可能超过int最大值，所以使用int保存结果
相加后需要对1000000007取余
代码
class Solution {public:int waysToStep(int n) {if (n < 3) return n;if (n == 3) return 4;vector<long long> dp(n+1, 0);// dp[i]表示爬到第i阶有多少方法dp[1] = 1;dp[2] = 2;dp[3] = 4;for (int i = 4; i <= n; ++i) {dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % 1000000007;}return dp[n];}};