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

示例1:

输入：n = 3
输出：4
说明: 有四种走法
示例2:

输入：n = 5
输出：13
提示:

n范围在[1, 1000000]之间

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/three-steps-problem-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

  1. class Solution {
  2.     public int waysToStep(int n) {
  3.         int[] result = new int[n+5];
  4.         result[0] = 0;
  5.         result[1] = 1;
  6.         result[2] = 2;
  7.         result[3] = 4;
  8.         for(int i =4;i<=n;i++){
  9.             result[i] = (result[i-1] + (result[i-2] + result[i-3])%1000000007)%1000000007;
  10.         }
  11.         return result[n];
  12.     }
  13. }

为什么要取模

取模，对两个较大的数之和取模再对整体取模，防止越界（这里也是有讲究的）
假如对三个dp[i-n]都 % 1000000007，那么也是会出现越界情况（导致溢出变为负数的问题）
因为如果本来三个dp[i-n]都接近 1000000007 那么取模后仍然不变，但三个相加则溢出
但对两个较大的dp[i-n]:dp[i-2],dp[i-3]之和mod 1000000007，那么这两个较大的数相加大于 1000000007但又不溢出
取模后变成一个很小的数，与dp[i-1]相加也不溢出
所以取模操作也需要仔细分析

为什么取模要使用1000000007

1.1000000007是一个质数
2.int32位的最大值为2147483647，所以对于int32位来说1000000007足够大
3.int64位的最大值为2^63-1，对于1000000007来说它的平方不会在int64中溢出
所以在大数相乘的时候，因为(a∗b)%c=((a%c)∗(b%c))%c，所以相乘时两边都对1000000007取模，再保存在int64里面不会溢出

1e9+9貌似也可以 。。。没有实际测试过

————————————————
版权声明：本文为CSDN博主「柳婼」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/liuchuo/article/details/51994215