【动态规划】-- 三步问题（easy）

1. 题目

在线oj
三步问题。有个小孩正在上楼梯，楼梯有 n 阶台阶，小孩一次可以上 1 阶、2 阶或 3 阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模 1000000007。

示例 1：

 输入：n = 3 输出：4说明：有四种走法

示例 2：

 输入：n = 5输出：13

提示:

1. n 范围在[1, 1000000]之间

2. 题目解析

1. 状态表示
经验 + 题目要求：以i位置为结尾，…
dp[ i ] 表示：到达 i 级台阶有dp[ i ] 种方法。
2. 状态转移方程

以 i 位置的状态，最近的一步来划分问题。

dp[ i ] :

1. 从（i- 1）位置到 i 位置
2. 从（i- 2）位置到 i 位置
3. 从（i- 3）位置到 i 位置
   

dp[ i ] = dp[ i - 1] + dp[ i - 2 ] + dp[ i - 3]

3. 初始化
dp[ 1 ] = 1;
dp[ 2 ] = 2;
dp[ 3 ] = 4;

4. 填表顺序
从左往右

5. 返回值
dp[n]

3. 代码

class Solution {public int waysToStep(int n) {//处理边界情况if (n == 1){return 1;}if (n == 2){return 2;}if (n == 3){return 4;}int MOD = (int) 1e9 + 7;//1. dp表int[] dp = new int[n + 1];//2. 初始化dp[1] = 1;dp[2] = 2;dp[3] = 4;//3. 填表for (int i = 4; i <= n  ; i++) {dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;}//4. 返回值return dp[n];}
}