Leetcode70 (Advanced), 322

70. climb stairs ( Advanced )

 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 ？

 

 Example  1：

 Input ：n = 2
 Output ：2
 explain ： There are two ways to climb to the top .
1. 1  rank  + 1  rank 
2. 2  rank 
 Example  2：

 Input ：n = 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 
 

 Tips ：

1 <= n <= 45

analysis

• Advanced ： First use the solution of complete knapsack , And then expand to every walk 1,2,3…m A ladder （ The title is 1,2 individual ）, That is, the template for finding a general solution
• When we did this problem before , Through inductive analysis , Using recurrence formula , Dynamic programming yields a Fibonacci sequence . See the link for details leetcode70,746
• Now let's look at the topic , In fact, I'm asking how many ways I can climb to the n Steps （ That is, how many ways to fill your backpack ）, It could be a combination , It may also be an arrangement , We need to give an example to verify .
• For example, the third step , It can be for （2,1） It can also be for （1,2）, These two ways are different , So make sure this is a The problem of permutation
• dp[j] The capacity is j My backpack is full of dp[j] Ways of planting
• The traversal order is double positive loop ： Backpack first , Post item
• Array initialization dp[0] = 1
• If you change it, you can 3,4,5…m steps , Just modify the last range of the item line .
• Actually , The above problems can also be abstracted into subset summation problems , That is, items are a collection , The number of steps is the target and .( And leetcode577 similar )leetcode518,377

Code （ Dynamic programming ）

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0]*(n+1)

        dp[0] = 1

        for i in range(1,n+1): #  Backpack first 
            for j in range(1,3): #  Post item ( Only one walk 、 Two steps )
                if i >= j: #  If the backpack mass is greater than or equal to the item  
                    dp[i] += dp[i-j]

        return dp[n]

Through screenshots

322. Change for

 Give you an array of integers  coins , Coins of different denominations ; And an integer  amount , Represents the total amount .

 Calculate and return the amount needed to make up the total amount   The minimum number of coins  . If no combination of coins can make up the total amount , return  -1 .

 You can think of the number of coins of each kind as infinite .

 

 Example  1：

 Input ：coins = [1, 2, 5], amount = 11
 Output ：3 
 explain ：11 = 5 + 5 + 1
 Example  2：

 Input ：coins = [2], amount = 3
 Output ：-1
 Example  3：

 Input ：coins = [1], amount = 0
 Output ：0
 

 Tips ：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

analysis （ Dynamic programming ）

• For the first time in dynamic programming , Find the least number of questions , What we think of is the problem of finding the maximum number before .
• First , Coin infinity , Abstract into a complete knapsack problem .
• dp[j] Express ： The total amount is j The minimum number of coins required is dp[j]
• Double forward traversal , Outer objects , Inner backpack , The starting point of the backpack , Start with the weight of the item , That is, the backpack can hold the item
• Compare the minimum , First of all, affirm your participation , Secondly, there is the minimum value of the previous state +1（ Add one more number to meet the backpack capacity ）, namely dp[j] = min(dp[j],dp[j-nums[i]]+1), initial value dp[0] = 0, Be sure to set , Otherwise, there will be problems in the comparison process .
• Because the comparison is the minimum , So I initialize it all as backpack space +1（ Equivalent to the maximum value of this question ）, As before, find the maximum , We initialize to 0 equally . avoid max,min Cause abnormal .
• therefore , Finally, if the value I asked for is equal to the value I set, it means that there is no result , return -1

Code

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:

        # dp[j]: Capacity of j The minimum number of coins used in your backpack is dp[j]
        dp = [amount+1]*(amount+1)
        dp[0] = 0
        for i in range(len(coins)): #  Traverse the items 
            for j in range(coins[i],amount+1): #  Traverse the backpack 
                dp[j] = min(dp[j],dp[j-coins[i]]+1)

        if dp[amount] == amount+1:
            return -1
        return dp[amount]

Through screenshots

If there is a mistake , Please correct me , Welcome to exchange , thank you *(･ω･)ﾉ