README.md

面试题 08.01. 三步问题

English Version

题目描述

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

示例1:

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

示例2:

 输入：n = 5
 输出：13

提示:

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

解法

递推法。f(n)=f(n-1)+f(n-2)+f(n-3)

Python3

class Solution:
    def waysToStep(self, n: int) -> int:
        if n < 3:
            return n
        a, b, c = 1, 2, 4
        for _ in range(4, n + 1):
            a, b, c = b, c, (a + b + c) % 1000000007
        return c

Java

class Solution {
    public int waysToStep(int n) {
        if (n < 3) {
            return n;
        }
        int a = 1, b = 2, c = 4;
        for (int i = 4; i <= n; ++i) {
            int t = a;
            a = b;
            b = c;
            c = ((a + b) % 1000000007 + t) % 1000000007;
        }
        return c;
    }
}

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
var waysToStep = function (n) {
    if (n < 3) return n;
    let a = 1,
        b = 2,
        c = 4;
    for (let i = 3; i < n; i++) {
        [a, b, c] = [b, c, (a + b + c) % 1000000007];
    }
    return c;
};

C

int waysToStep(int n) {
    if (n < 3) {
        return n;
    }
    int a = 1, b = 2, c = 4, i = 4;
    while (i++ <= n) {
        int t = ((a + b) % 1000000007 + c) % 1000000007;
        a = b;
        b = c;
        c = t;
    }
    return c;
}

C++

class Solution {
public:
    int waysToStep(int n) {
        if (n < 3) {
            return n;
        }
        int a = 1, b = 2, c = 4, i = 4;
        while (i++ <= n) {
            int t = ((a + b) % 1000000007 + c) % 1000000007;
            a = b;
            b = c;
            c = t;
        }
        return c;
    }
};

Rust

impl Solution {
    pub fn ways_to_step(n: i32) -> i32 {
        let mut dp = [1, 2, 4];
        let n = n as usize;
        if n <= 3 {
            return dp[n - 1];
        }
        for _ in 3..n {
            dp = [
                dp[1],
                dp[2],
                (((dp[0] + dp[1]) % 1000000007) + dp[2]) % 1000000007,
            ];
        }
        dp[2]
    }
}