LeetCode刷题（76）～三步问题

题目描述

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

示例1:

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

示例2:

输入：n = 5
 输出：13

提示:

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

解答 By 海轰

提交代码（动态规划 注：数字非常大 题目提示进行取模运算）

int waysToStep(int n) {
      if(n==1) return 1;
      if(n==2) return 2;
      if(n==3) return 4;
      int num1=1;
      int num2=2;
      int num3=4;
      for(int i=4;i<=n;++i)
      {
         int temp=(num1+(num2+num3)%1000000007)%1000000007;
         num1=num2;
         num2=num3;
         num3=temp;
      }
      return num3;     
    }

运行结果

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/three-steps-problem-lcci