By Ne0 — May 20, 2024

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;
    }
}