LeetCode 面试题 08.01. 三步问题

一、题目

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

示例1:

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

示例2:

输入： n = 5
输出： 13

提示:

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

  点击此处跳转题目。

二、Java 题解

  比较简单，直接上代码了。有点类似斐波那契数列。

class Solution {public int waysToStep(int n) {int ans = 4;int[] f = new int[] { 1, 2, 4 };if (n < 3) return f[n - 1];while (n > 3) {ans = ((f[0] + f[1]) % 1000000007 + f[2]) % 1000000007; f[0] = f[1];f[1] = f[2];f[2]= ans;n--;}return ans;}
}

• 时间：14 ms，击败 75.78% 使用 Java 的用户
• 内存：37.17 MB，击败 85.21% 使用 Java 的用户