# 0322-零钱兑换(0322 – change)-其他

## 0322-零钱兑换(0322 – change)

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

• https://leetcode-cn.com/problems/coin-change/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-wan-q-80r7/

### python

``````# 0322.零钱兑换

class Solution:
def coinChange(self, coins: [int], amount: int) -> int:
"""
动态规划，完全背包，先遍历物品再遍历背包
:param coins:
:param amount:
:return:
"""
dp = [amount+1] * (amount+1)
dp[0] = 0
for coin in coins:
for j in range(coin, amount+1):
dp[j] = min(dp[j], dp[j-coin]+1)
print(" dp[%d]: %d  |" % (j, dp[j]), end=' ')
return dp[amount] if dp[amount] < amount+1 else -1

def coinChange2(self, coins: [int], amount: int) -> int:
"""
动态规划，完全背包，先背包再物品
:param coins:
:param amount:
:return:
"""
dp = [amount+1] * (amount+1)
dp[0] = 0
for j in range(1, amount+1):
for i in range(len(coins)):
if j >= coins[i]:
dp[j] = min(dp[j], dp[j-coins[i]]+1)
return dp[amount] if dp[amount] < amount+1 else -1

if __name__ == "__main__":
coins = [346,29,395,188,155,109]
test = Solution()
test.coinChange(coins, 9401)
``````

### golang

``````package dynamicPrograming

import "math"

// 动态规划-完全背包-先物品再背包
func coinChange(coins []int, amount int) int  {
dp := make([]int, amount+1)
dp[0] = 0
for j:=1;j<=amount;j++ {
dp[j] = math.MaxInt32
}
// 遍历物品
for i:=0;i<len(coins);i++ {
for j:=coins[i];j<=amount;j++ {
if dp[j-coins[i]] != math.MaxInt32 {
dp[j] = min(dp[j], dp[j-coins[i]]+1)
}
}
}
if dp[amount] == math.MaxInt32 {
return -1
}
return dp[amount]
}

// 动态规划-完全背包-先背包再物品
func coinChange2(coins []int, amount int) int {
dp := make([]int, amount+1)
dp[0] = 0
for j:=1;j<=amount;j++ {
dp[j] = math.MaxInt32
for i:=0;i<len(coins);i++ {
if j >= coins[i] && dp[j-coins[i]] != math.MaxInt32 {
dp[j] = min(dp[j], dp[j-coins[i]]+1)
}
}
}
if dp[amount] == math.MaxInt32 {
return -1
}
return dp[amount]
}

func min(a,b int) int {
if a < b {
return a
}
return b
}
``````
————————

Give you an integer array of coins to represent coins of different denominations; And an integer amount representing the total amount.

Calculate and return the minimum number of coins required to make up the total amount. If no coin combination can form a total amount, return  – 1 。

You can think that the number of each coin is unlimited.

Example   1：

Input: Coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:

Input: Coins = [2], amount = 3
Output: – 1
Example 3:

Input: Coins = [1], amount = 0
Output: 0
Example 4:

Input: Coins = [1], amount = 1
Output: 1
Example 5:

Input: Coins = [1], amount = 2
Output: 2

Tips:

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

reference resources:

• https://leetcode-cn.com/problems/coin-change/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-wan-q-80r7/

### python

``````# 0322.零钱兑换

class Solution:
def coinChange(self, coins: [int], amount: int) -> int:
"""
动态规划，完全背包，先遍历物品再遍历背包
:param coins:
:param amount:
:return:
"""
dp = [amount+1] * (amount+1)
dp[0] = 0
for coin in coins:
for j in range(coin, amount+1):
dp[j] = min(dp[j], dp[j-coin]+1)
print(" dp[%d]: %d  |" % (j, dp[j]), end=' ')
return dp[amount] if dp[amount] < amount+1 else -1

def coinChange2(self, coins: [int], amount: int) -> int:
"""
动态规划，完全背包，先背包再物品
:param coins:
:param amount:
:return:
"""
dp = [amount+1] * (amount+1)
dp[0] = 0
for j in range(1, amount+1):
for i in range(len(coins)):
if j >= coins[i]:
dp[j] = min(dp[j], dp[j-coins[i]]+1)
return dp[amount] if dp[amount] < amount+1 else -1

if __name__ == "__main__":
coins = [346,29,395,188,155,109]
test = Solution()
test.coinChange(coins, 9401)
``````

### golang

``````package dynamicPrograming

import "math"

// 动态规划-完全背包-先物品再背包
func coinChange(coins []int, amount int) int  {
dp := make([]int, amount+1)
dp[0] = 0
for j:=1;j<=amount;j++ {
dp[j] = math.MaxInt32
}
// 遍历物品
for i:=0;i<len(coins);i++ {
for j:=coins[i];j<=amount;j++ {
if dp[j-coins[i]] != math.MaxInt32 {
dp[j] = min(dp[j], dp[j-coins[i]]+1)
}
}
}
if dp[amount] == math.MaxInt32 {
return -1
}
return dp[amount]
}

// 动态规划-完全背包-先背包再物品
func coinChange2(coins []int, amount int) int {
dp := make([]int, amount+1)
dp[0] = 0
for j:=1;j<=amount;j++ {
dp[j] = math.MaxInt32
for i:=0;i<len(coins);i++ {
if j >= coins[i] && dp[j-coins[i]] != math.MaxInt32 {
dp[j] = min(dp[j], dp[j-coins[i]]+1)
}
}
}
if dp[amount] == math.MaxInt32 {
return -1
}
return dp[amount]
}

func min(a,b int) int {
if a < b {
return a
}
return b
}
``````