面试题 08.01. 三步问题

题

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

示例1:

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

输入：n = 5
输出：13

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/three-steps-problem-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

ans[n]=上3步之和

代码

class Solution:
    def waysToStep(self, n: int) -> int:
        # 1 2 3
        MOD_DATA = 1000000007
        ans = [1, 2, 4]
        # 注意我定义0为1 n-1 是n
        for i in range(3, n):
            index = i % 3
            ans[index] = (ans[index - 1] + ans[index - 2] + ans[index - 3]) % MOD_DATA
        return ans[(n-1)%3]