Leetcode面试题-0801-三步问题-Python实现

• 题目要求：

• 思路：

  • 上第一个台阶有一种方法：（1）1
  • 上第二个台阶有两种方法：（1）1+1（2）2
  • 上第三个台阶有四种方法：（1）1+1+1（2）1+2（3）2+1（4）3
  • 所以从上第四个台阶开始，就可以依据前面的数据进行计算，比如上第四个台阶，可以从第一个台阶一次走三步上来，也可以从第二个台阶一次走两步上来，也可以第三个台阶一次走一步上来，所以走第四个台阶的方法总数是（台阶 1 的方法 + 台阶 2 的方法 + 台阶 3 的方法）
  • 从台阶 4 开始的每一个台阶，都可以根据当前台阶的前三个台阶的方法数和求来，所以只需要维护当前台阶的前三个台阶数即可
• 核心代码：

if n <= 2:
    return n
step1, step2, step3 = 1, 2, 4
for i in range(3, n):
    step1, step2, step3 = step2 % 1000000007, step3 % 1000000007, (step1 + step2 + step3) % 1000000007
return step3

• 完整代码：

class Solution:
    def waysToStep(self, n: int) -> int:
        if n <= 2:
            return n
        step1, step2, step3 = 1, 2, 4
        for i in range(3, n):
            step1, step2, step3 = step2 % 1000000007, step3 % 1000000007, (step1 + step2 + step3) % 1000000007
        return step3