面试题 08.01. 三步问题

Posted on | In
Words count in article: 185 | Reading time ≈ 1

题目

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

示例1：

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

示例2：

1
2
输入：n = 5
输出：13

提示：

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

解法

解法一：

变形的Fibonacci数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int waysToStep(int n) {
        int result = 0;
        if (1 == n) {
            return 1;
        } else if (2 == n) {
            return 2;
        } else if (3 == n) {
            return 4;
        }
        int r1 = 1;
        int r2 = 2;
        int r3 = 4;
        for (int i = 4;i <= n;i++) {
            result = (((r1 + r2) % 1000000007) + r3) % 1000000007;
            r1 = r2;
            r2 = r3;
            r3 = result;
        }
        return result;
    }
0%