动态规划（1）（java）（面试题）三步问题

题目:

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

示例 1：

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

示例 2：

 输入：n = 5
 输出：13

解法思路：

1--状态表示：

        经验+题目要求

        以i位置为结尾。。。。

        dp【i】表示：到达i位置时，一共有多少种方法

2--状态转移方程

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

3--初始化

4--填表顺序

5--返回值

实现：

public class Solution {public int waysToStep(int n) {int MOD = (int) 1e9 + 7;//防止溢出//处理边界的情况if (n == 1 || n == 2) return n;if (n == 3) return 4;int[] dp = new int[n + 1];dp[1] = 1;dp[2] = 2;dp[3] = 4;for (int i = 4; i <=n; i++) {dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3] % MOD);}return dp[n];}public static void main(String[] args) {Solution solution = new Solution();int n=4;System.out.println(solution.waysToStep(n));}
}