当前位置：网站首页>Leetcode: countless denominations of coins get the option of amount (DP)

Leetcode: countless denominations of coins get the option of amount (DP)

2022-04-21 13:16:00 【Review of the white speed Dragon King】

Insert picture description here

analysis

In order First traversal amount And then iterate through each coin That's all right.
If calculated by combination Suppose you choose coins[i], that j From coins[i] To amount Add up dp[j]

code comparison

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        ''' #  This is calculated in order  dp = [0] * (amount + 1) dp[0] = 1 #  There's always a way to choose nothing  for i in range(1, amount + 1): for coin in coins: if i >= coin: dp[i] += dp[i - coin] return dp[-1] '''

        #  This is calculated by combination 
        dp = [0] * (amount + 1)
        dp[0] = 1 #  There's always a way to choose nothing 

        n = len(coins)

        #  Chose one coins[i]
        #  Always choose coins[i]
        for i in range(n):
            for j in range(coins[i], amount + 1):
                dp[j] += dp[j - coins[i]]
        
        return dp[-1]