Three step problem of leetcode

subject

Three step problem . There is a child going up the stairs , The stairs have n Steps , Children can go to 1 rank 、2 Step or 3 rank . Implement a way , Calculate how many ways a child can go up stairs . The results could be big , You need to model the results 1000000007.

Example 1:

  Input ：n = 3 
  Output ：4
  explain : There are four ways to walk
Example 2:

  Input ：n = 5
  Output ：13

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/three-steps-problem-lcci
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas

Like a frog jumping on a step , First write the results of the previous steps ：

  Through these results , You can find the law ：

f(n)=f(n-1)+f(n-2)+f(n-3) (n≥3, And f(0)=f(1)=1,f(2)=2), With this rule , The code is easy to write ！

Maybe , Some of them will say , How do you know that you can get the right result by finding the rules from the beginning ？ In fact, I didn't know at first , It is with a try attitude （ Because I was doing “ Frogs jump the steps ” I learned this method when I was , And this topic is very similar to it , So it's easy to think of this method by analogy ！ therefore , The kingcraft of problem solving ： Do more , How to summarize .）

Source code

class Solution:
    #  It is similar to climbing only one or two stairs at a time , Find out the rules , Find out ：f(n)=f(n-1)+f(n-2)+f(n-3) (n≥3, And f(0)=f(1)=1,f(2)=2)
    def waysToStep(self, n: int) -> int:
        if n == 1: return 1
        if n == 2: return 2
        n0, n1, n2 = 1, 1, 2
        for i in range(n - 2):
            n0, n1, n2 = n1, n2, (n0 + n1 + n2) % 1000000007
            # print(n2)

        return n2

Through screenshots

  Synchronous update in personal blog system ：LeetCode The third step