LeetCode 322. Coin Change
Description
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
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
Note:
You may assume that you have an infinite number of each kind of coin.
描述
給定不同面額的硬幣 coins 和一個總金額 amount闸盔。編寫一個函數(shù)來計(jì)算可以湊成總金額所需的最少的硬幣個數(shù)高帖。如果沒有任何一種硬幣組合能組成總金額，返回 -1。
示例 1:
輸入: coins = [1, 2, 5], amount = 11
輸出: 3
解釋: 11 = 5 + 5 + 1
示例 2:
輸入: coins = [2], amount = 3
輸出: -1
說明:
你可以認(rèn)為每種硬幣的數(shù)量是無限的焦人。
思路
- 這道題目使用動態(tài)規(guī)劃坯苹。
- 對于要兌換面值為 a 的硬幣篓冲，我們從面值為 0 的硬幣開始找表蝙，一路規(guī)劃到 a。
- 狀態(tài)：matrix[i][j],表示使用 coins 的前 i 個硬幣劫映，兌換面值為 j 的硬幣所需要的硬幣的個數(shù)违孝。
- 狀態(tài)轉(zhuǎn)移：
- 對于面值的 k 的硬幣，假設(shè)此時我們已經(jīng)使用了 coins 的前 i 個銀幣泳赋，則
- 1.我們可以把 k 拆分成 k - coins[i] + coins[i]雌桑，即需要面值為 k - coins[i] 的硬幣需要兌換的硬幣個數(shù) + 1；
- 2.我們也可以不使用當(dāng)前的硬幣祖今，那么兌換面值為 k 的硬幣就需要使用前 i-1 個硬幣兌換面值為 k 的硬幣的個數(shù)校坑；
- 我們?nèi)〕錾厦鎯煞N情況的最小值。
- 結(jié)果：矩陣的最后一個值千诬。
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2019-03-01 10:21:19
# @Last Modified by: 何睿
# @Last Modified time: 2019-03-01 14:33:42
class Solution:
def coinChange(self, coins: [int], amount: int) -> int:
# 聲明一個二維矩陣
matrix = [[i for i in range(amount + 1)] for _ in range(2)]
# 初始化第一行
for i in range(amount + 1):
# 如果當(dāng)前位置表示的需要兌換的錢數(shù)可以被整除耍目，將當(dāng)前位置置為需要錢的個數(shù)
if i % coins[0] == 0:
matrix[0][i] = i // coins[0]
# 否則將當(dāng)前的錢數(shù)目置為 amount+1
else:
matrix[0][i] = amount + 1
for i in range(1, len(coins)):
for j in range(amount + 1):
row = i % 2
# 不使用第 i 個硬幣，僅使用 i 前面的所有硬幣
# 則一共需要當(dāng)前行上一行對應(yīng)位置的硬幣
top = matrix[(i - 1) % 2][j]
# 使用當(dāng)前的硬幣大渤，如果當(dāng)前需要兌換的硬幣面值大于當(dāng)前硬幣的面值
if j >= coins[i]:
# 動態(tài)規(guī)劃：兌換面值為 a 的硬幣制妄，在已經(jīng)使用了coins[0:col-1]這些硬幣的情況下
# 可以由 a - coins[col] 需要的硬幣加上硬幣 coins[col]，
# 所以需要的硬幣個數(shù)為 matrix[row][a - coins[col]]+1泵三；
# 也可以不使用當(dāng)前的硬幣，僅僅使用前 i 個硬幣
# 那么需要的硬幣個數(shù)為 matrix[row-1][col]
# 取出最下值
matrix[row][j] = min(top, matrix[row][j - coins[i]] + 1)
else:
matrix[i % 2][j] = top
res = 0
# 為了節(jié)省空間衔掸，我們的矩陣僅僅使用了兩行烫幕，
# 如果 coins 的個數(shù)為奇數(shù)個，那么最終結(jié)果在第一行
if len(coins) % 2:
res = -1 if matrix[0][-1] == amount + 1 else matrix[0][-1]
# 如果 coins 的個位數(shù)為偶數(shù)個敞映，那么最終結(jié)果為第二行
else:
res = -1 if matrix[1][-1] == amount + 1 else matrix[1][-1]
return res
def coinChange2(self, coins: [int], amount: int) -> int:
# 思路同方法一完全一樣较曼，僅僅是換了一種寫的方式
# python 對于列表解析式的執(zhí)行效率更快
count = amount + 1
line = [i for i in range(count)]
for i in range(1, count):
line[i] = min(line[i - c] if i >= c else count for c in coins)
if line[i] != count: line[i] += 1
return line[-1] if line[-1] != count else -1
源代碼文件在 這里 。
?本文首發(fā)于 何睿的博客 振愿，歡迎轉(zhuǎn)載捷犹，轉(zhuǎn)載需保留 文章來源 ，作者信息和本聲明.
微信公眾號：techruicore
