dialy_leetcode_面试题0801-三步问题

1 题目描述

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

2 题解

2.1 动态规划

斐波那契问题，只不过变成了三项，有个坑就是，整数溢出的问题，所以在两项相加后就需要进行去摸操作，防止溢出。

class Solution:
    def waysToStep(self, n: int) -> int:

        if n < 3:
            return n
        if n == 3:
            return 4

        d1, d2, d3 = 1, 2, 4
        res = 0

        for val in range(n-3):
            res = (d1 + d2) % 1000000007 + d3
            res %= 1000000007
            d1, d2, d3, = d2, d3, res

        return res