leetcode518,377

518. Change for II

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

 Please calculate and return the number of coin combinations that can be rounded up to the total amount . If no combination of coins can make up the total amount , return  0 .

 Suppose that there are infinite coins of each denomination . 

 The subject data ensure that the results meet  32  Bit signed integer .

 

 Example  1：

 Input ：amount = 5, coins = [1, 2, 5]
 Output ：4
 explain ： There are four ways to make up the total amount ：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
 Example  2：

 Input ：amount = 3, coins = [2]
 Output ：0
 explain ： Use only face value  2  We can't make up the total amount of  3 .
 Example  3：

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

 Tips ：

1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins  All the values in   Different from each other 
0 <= amount <= 5000

analysis

• If you want to calculate every possible set , You need a backtracking algorithm , If only counting , Dynamic planning .
• Abstract problem ： Completely backpack （ Because a number can be taken many times ）
• Find the total number ： Combination question ,dp[j] = dp[j-nums[i]]
• initialization ：dp[0] = 1
• traversal order , Double forward , Order doesn't matter
• dp[j] Express ： Capacity of j My backpack has dp[j] A way to fill your backpack

Code

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # amount： Indicates the maximum capacity of the backpack 
        # coins: Indicates an item 
        dp = [0] * (amount+1) # dp[j] Indicates that the full capacity is j The possibility of backpacking 
        dp[0] = 1
        for i in coins: #  Traverse the items 
            for j in range(i,amount+1): #  Traverse the backpack 
                dp[j] += dp[j-i]

        return dp[amount]

Through screenshots

377. Combinatorial summation Ⅳ

 Here you are   Different   An array of integers  nums , And a target integer  target . Please start from  nums  Find and return the sum of  target  The number of element combinations of .

 The data of the questions ensure that the answers are in line with  32  Bit integer range .

 

 Example  1：

 Input ：nums = [1,2,3], target = 4
 Output ：7
 explain ：
 All possible combinations are ：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
 Please note that , Different sequences are considered as different combinations .
 Example  2：

 Input ：nums = [9], target = 3
 Output ：0
 

 Tips ：

1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums  All elements in   Different from each other 
1 <= target <= 1000

analysis

• Abstract problem ： Completely backpack （ Because a number can be taken many times ）
• Find the total number ： Here is the case output , Knowing is a permutation problem
• initialization ：dp[0] = 1
• traversal order , We said that the complete knapsack problem is generally double positive order , There is no difference between the inner and outer layers of items and backpacks . however , In this question , The backpack must be on the outer layer , Items are inside . Think about it a little bit , Arrangement is the case of different order , If you put the object on the outer layer , Anyway, the order of items is fixed . So put the items on the inner layer , The item is traversed many times , In a different order .
• dp[j] Express ： Capacity of j My backpack has dp[j] A way to fill your backpack .
• Because it is a forward traversal , Pay attention to the starting position , But since we started with backpacks , So I can't determine which position is more suitable at the beginning , So after the double cycle, we must judge the relationship between the size of the item and the backpack .

Code

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:

        #  Completely backpack 
        # nums: goods 
        # target: The maximum capacity of the backpack 
        # dp[j]: The capacity of the backpack is j Number of permutations of 

        dp = [0] *(target+1)
        dp[0] = 1
        for i in range(1,target+1): #  Traverse the backpack 
            for j in range(len(nums)): #  Traverse the items 
                if nums[j] <= i: #  When items can be put into backpacks 
                    dp[i] += dp[i-nums[j]]

        return dp[target]

Through screenshots

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