leetcode 面试题 08.01. 三步问题 动态规划 自下而上 爬楼梯类型

类比斐波那锲数列

题目：

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

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

示例2: 输入：n = 5 输出：13

提示: n范围在[1, 1000000]之间

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/three-steps-problem-lcci

思路： 时间复杂度O(n)，空间复杂度O(n)。

代码：

class Solution(object):
    def waysToStep(self, n):
        """
        :type n: int
        :rtype: int
        """

        if n==1:
            return 1
        if n==2:
            return 2
        if n==3:
            return 4

        dp=[0]*1000001
        dp[1]=1
        dp[2]=2
        dp[3]=4

        for i in range(4,n+1):
            dp[i]=(dp[i-1]+dp[i-2]+dp[i-3])%1000000007
        
        return dp[n]


**本博客为原创作品，欢迎指导,转载请说明出处，附上本文链接，谢谢！**