Recommend a song every day ： Thousands of miles away ——Jay Chou

The following is my Ladder integral rule ：

At least one question a day ： An integral +10 branch
If you do one more question （ Or one more way to answer ）, Then the points of the day +20 branch （+10+10）
If you do more than three , Start with question 3 +20 branch （ Such as ： If you do three questions, you will score -10+10+20=40; If you do four questions, you will score –10+10+20+20=60）

---

Initial classification 100 branch
If you haven't done the problem for one day , Then deduct points -10 branch （ Saturday 、 Except Sunday ： rest ）
insist ！！！

Primary algorithm

List of questions

Dynamic programming

stem

Suppose you're climbing the stairs . need n You can reach the top of the building .

Every time you climb 1 or 2 A stair . How many different ways can you climb to the top of the building ？

Be careful ： Given n Is a positive integer .

Example 1：

Input ： 2
Output ： 2
explain ： There are two ways to climb to the top .

1. 1 rank + 1 rank
2. 2 rank

Example 2：

Input ： 3
Output ： 3
explain ： There are three ways to climb to the top .

1. 1 rank + 1 rank + 1 rank
2. 1 rank + 2 rank
3. 2 rank + 1 rank

recursive

analysis ：

Some big guys said that the principle of this problem is the same as that of frog platform jumping .

• When n=1 when , Just once ,f(1)=1;
• When n=2 when , There can be two ,f(2)=2;
• When n=3 when , Three times ,f(3)=f(2)+f(1);

Borrow the picture ：

class Solution: def climbStairs(self, n: int) -> int: # recursive  if n <= 1: return 1 if n < 3: return n return Solution.climbStairs(self, n-1) + Solution.climbStairs(self, n-2)

Direct timeout , This recursion , A little slow ！

There's still no recursion here , Use non recursive .

Non recursive

In fact, it is also the one used Fibonacci Methods .

class Solution: def climbStairs(self, n: int) -> int: if n <=2: return n l = [1, 2] for i in range(n-2): l.append(l[i]+l[i+1]) return l[n-1]

The speed is obviously up .

In fact, there are many ways , You can try .

Continue to read the paper o(╥﹏╥)o

Reference

author ： Power button (LeetCode)
link ：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnumcr/
source ： Power button （LeetCode）

author ： Data structures and algorithms
link ：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn854d/?discussion=DW6hWu
source ： Power button （LeetCode）

Score today ：+10+10
Total score ：760

come on. ！！！