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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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