許多人認為身上如果帶太多的零錢會讓行動變得不方便，因此會希望商店店員在找零錢的時候能夠以最少的硬幣數來找，而不是全部都用1元塞給我們。
這篇文章將會直接以動態規劃來解決問題，如果您還不熟悉動態規劃的話可以先查看這篇文章：
假設現在店家有1、5、10、25元面額的硬幣，不限數量，當店員要找給客人31元的時候，可以怎麼找？例如：
- 給31個1元。(那店員怕是要被揍了)
- 給1個25元、1個5元、1個1元。
- 給3個10元、1個1元。
店員如果是拿1個25元、1個5元、1個1元，只需要3枚硬幣就可以湊成31元，而客人拿了也會很開心。
您可能會覺得，這問題不是很簡單嗎？只要從最大面額開始找就好了。確實沒錯，但如果多了一種21元的硬幣面額會怎麼樣呢？
重新敘述問題：假設現在店家有1、5、10、21、25元面額的硬幣，不限數量，當店員要找給客人63元的時候，最少要多少個硬幣？
如果我們從最大面額開始找，需要2個25元，1個10元，3個3元，共6枚硬幣，但這個找法卻不是這個問題的最佳解……因為我們其實可以只用3個21元的硬幣來組成63元。當然，也是因為這個題目已經設計好的關係(63明顯就是21乘3)，才能讓我們快速地找出最佳解，如果換成其它數字，可能就不是那麼容易了。
以Top-down的方式來思考上面的問題。因為在最後一步要能夠以最少硬幣數湊出63元，而在執行最後一步前，有可能已經湊出了62元、58元、42元或是38元，所以要從0元湊到63元，最少的硬幣數就是湊到62元的最少硬幣數、湊到58元的最少硬幣數、湊到42元的最少硬幣數和湊到38元的最少硬幣數中的最小值再加1……依此類推。最小的問題為湊0元(最少需要0個硬幣)、湊1元(最少需要1個硬幣)和湊2 ~ 24元，但是湊2 ~ 24元我們不太能夠直接知道最少要幾個硬幣，所以不要把它當作是基本案例(base case)。
以程式來解題的話，我們可以寫出以下的遞迴函數：
pub fn change_coin(amount: usize) -> usize {
match amount {
0 => 0,
1 => 1,
_ => {
if amount < 25 {
if amount >= 21 {
change_coin(amount - 1).min(change_coin(amount - 5)).min(change_coin(amount - 10)).min(change_coin(amount - 21)) + 1
} else if amount >= 10 {
change_coin(amount - 1).min(change_coin(amount - 5)).min(change_coin(amount - 10)) + 1
} else if amount >= 5 {
change_coin(amount - 1).min(change_coin(amount - 5)) + 1
} else {
change_coin(amount - 1) + 1
}
} else {
change_coin(amount - 1).min(change_coin(amount - 5)).min(change_coin(amount - 10)).min(change_coin(amount - 21)).min(change_coin(amount - 25)) + 1
}
}
}
}
public static int changeCoin(final int amount) {
switch (amount) {
case 0:
return 0;
case 1:
return 1;
default:
if (amount < 25) {
if (amount >= 21) {
return Math.min(changeCoin(amount - 1), Math.min(changeCoin(amount - 5), Math.min(changeCoin(amount - 10), changeCoin(amount - 21)))) + 1;
} else if (amount >= 10) {
return Math.min(changeCoin(amount - 1), Math.min(changeCoin(amount - 5), changeCoin(amount - 10))) + 1;
} else if (amount >= 5) {
return Math.min(changeCoin(amount - 1), changeCoin(amount - 5)) + 1;
} else {
return changeCoin(amount - 1) + 1;
}
} else {
return Math.min(changeCoin(amount - 1), Math.min(changeCoin(amount - 5), Math.min(changeCoin(amount - 10), Math.min(changeCoin(amount - 21), changeCoin(amount - 25))))) + 1;
}
}
}
function changeCoin(amount: number): number {
switch (amount) {
case 0:
return 0;
case 1:
return 1;
default:
if (amount < 25) {
if (amount >= 21) {
return Math.min(changeCoin(amount - 1), Math.min(changeCoin(amount - 5), Math.min(changeCoin(amount - 10), changeCoin(amount - 21)))) + 1;
} else if (amount >= 10) {
return Math.min(changeCoin(amount - 1), Math.min(changeCoin(amount - 5), changeCoin(amount - 10))) + 1;
} else if (amount >= 5) {
return Math.min(changeCoin(amount - 1), changeCoin(amount - 5)) + 1;
} else {
return changeCoin(amount - 1) + 1;
}
} else {
return Math.min(changeCoin(amount - 1), Math.min(changeCoin(amount - 5), Math.min(changeCoin(amount - 10), Math.min(changeCoin(amount - 21), changeCoin(amount - 25))))) + 1;
}
}
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func ChangeCoin(amount int) int {
switch amount {
case 0:
return 0
case 1:
return 1
default:
if amount < 25 {
if amount >= 21 {
return min(ChangeCoin(amount-1), min(ChangeCoin(amount-5), min(ChangeCoin(amount-10), ChangeCoin(amount-21)))) + 1
} else if amount >= 10 {
return min(ChangeCoin(amount-1), min(ChangeCoin(amount-5), ChangeCoin(amount-10))) + 1
} else if amount >= 5 {
return min(ChangeCoin(amount-1), ChangeCoin(amount-5)) + 1
} else {
return ChangeCoin(amount-1) + 1
}
} else {
return min(ChangeCoin(amount-1), min(ChangeCoin(amount-5), min(ChangeCoin(amount-10), min(ChangeCoin(amount-21), ChangeCoin(amount-25))))) + 1
}
}
}
當然，這個函數的效能很差，先不管它。因為還有個更嚴重的地方，那就是這個程式目前只能固定地用1、5、10、21、25元面額的硬幣來計算，功能實在太弱了！所以我們要把程式改成可以從函數參數輸入硬幣的面額(假設至少有一種面額，每種面額至少會有1元，且會遞增輸入)。而因為輸入的最小面額可能會大於1元，所以需要注意到無解的情形(例如面額只有3元和7元，就不可能湊到11元)。若是無解，則把結果設為「最大整數」。
程式強化功能後如下：
pub fn change_coin(coin_kinds: &[usize], amount: usize) -> usize {
if amount < coin_kinds[0] {
if amount == 0 {
0
} else {
usize::max_value()
}
} else {
let mut min = usize::max_value() - 1;
for coin_kind in coin_kinds.iter().copied() {
if amount < coin_kind {
break;
}
min = min.min(change_coin(coin_kinds, amount - coin_kind));
}
return min + 1;
}
}
public static int changeCoin(final int[] coinKinds, final int amount) {
if (amount < coinKinds[0]) {
return amount == 0 ? 0 : Integer.MAX_VALUE;
} else {
int min = Integer.MAX_VALUE - 1;
for (final int coinKind : coinKinds) {
if (amount < coinKind) {
break;
}
min = Math.min(min, changeCoin(coinKinds, amount - coinKind));
}
return min + 1;
}
}
function changeCoin(coinKinds: number[], amount: number) {
if (amount < coinKinds[0]) {
return amount === 0 ? 0 : Number.MAX_SAFE_INTEGER;
} else {
let min = Number.MAX_SAFE_INTEGER - 1;
for (const coinKind of coinKinds) {
if (amount < coinKind) {
break;
}
min = Math.min(min, changeCoin(coinKinds, amount - coinKind));
}
return min + 1;
}
}
func ChangeCoin(coinKinds []int, amount int) int {
const MAX_UNIT = ^uint(0)
const MAX_INT = int(MAX_UNIT >> 1)
if amount < coinKinds[0] {
if amount == 0 {
return 0
} else {
return MAX_INT
}
} else {
min := MAX_INT - 1
for _, coinKind := range coinKinds {
if amount < coinKind {
break
}
a := ChangeCoin(coinKinds, amount-coinKind)
if min > a {
min = a
}
}
return min + 1
}
}
由於以上程式碼有重疊子問題，所以可以用動態規劃的記憶法來優化或是用製表法將其改寫成迭代函數。
以製表法為例，改寫如下：
pub fn change_coin(coin_kinds: &[usize], amount: usize) -> usize {
let mut dp = vec![usize::max_value(); amount + 1];
dp[0] = 0;
for i in coin_kinds[0]..=amount {
let mut min = usize::max_value() - 1;
for coin_kind in coin_kinds.iter().copied() {
if i < coin_kind {
break;
}
let remain_amount = i - coin_kind;
if min > dp[remain_amount] {
min = dp[remain_amount];
}
}
dp[i] = min + 1;
}
dp[amount]
}
以上程式，故意不使用程式語言內建的min函數來取最小值，因為之後我們會在if區塊內添加程式敘述。
public static int changeCoin(final int[] coinKinds, final int amount) {
final int[] dp = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = coinKinds[0]; i <= amount; ++i) {
int min = Integer.MAX_VALUE - 1;
for (final int coinKind : coinKinds) {
if (i < coinKind) {
break;
}
final int remainAmount = i - coinKind;
if (min > dp[remainAmount]) {
min = dp[remainAmount];
}
}
dp[i] = min + 1;
}
return dp[amount];
}
以上程式，故意不使用程式語言內建的min函數來取最小值，因為之後我們會在if區塊內添加程式敘述。
function changeCoin(coinKinds: number[], amount: number) {
const dp = new Array<number>(amount + 1).fill(Number.MAX_SAFE_INTEGER);
dp[0] = 0;
for (let i = coinKinds[0];i <= amount;++i) {
let min = Number.MAX_SAFE_INTEGER - 1;
for (const coinKind of coinKinds) {
if (i < coinKind) {
break;
}
const remainAmount = i - coinKind;
if (min > dp[remainAmount]) {
min = dp[remainAmount];
}
}
dp[i] = min + 1;
}
return dp[amount];
}
以上程式，故意不使用程式語言內建的min函數來取最小值，因為之後我們會在if區塊內添加程式敘述。
func ChangeCoin(coinKinds []int, amount int) int {
const MAX_UNIT = ^uint(0)
const MAX_INT = int(MAX_UNIT >> 1)
dp := make([]int, amount+1)
for i := 0; i <= amount; i++ {
dp[i] = MAX_INT
}
dp[0] = 0
for i := coinKinds[0]; i <= amount; i++ {
min := MAX_INT - 1
for _, coinKind := range coinKinds {
if i < coinKind {
break
}
remainAmount := i - coinKind
if min > dp[remainAmount] {
min = dp[remainAmount]
}
}
dp[i] = min + 1
}
return dp[amount]
}
dp陣列的索引i所儲存的值就是湊到i元時最少需要的硬幣數量。
接著我們就要來利用上面這支程式去取得最少硬幣數量的組合方式了。
為了讓各位充分理解上面這支程式的用途，就先把程式改為直接在螢幕上輸出結果，而不是透過函數回傳出來。程式碼如下：
pub fn change_coin(coin_kinds: &[usize], amount: usize) {
let mut dp = vec![usize::max_value(); amount + 1];
dp[0] = 0;
for i in coin_kinds[0]..=amount {
let mut min = usize::max_value() - 1;
for coin_kind in coin_kinds.iter().copied() {
if i < coin_kind {
break;
}
let remain_amount = i - coin_kind;
if min > dp[remain_amount] {
min = dp[remain_amount];
}
}
dp[i] = min + 1;
}
for (a, min_count) in dp.into_iter().enumerate() {
if min_count == usize::max_value() {
println!("For amount {}, there is no solution.", a);
continue;
}
println!("For amount {}, the minimum number of coins is {}.", a, min_count);
}
}
public static void changeCoin(final int[] coinKinds, final int amount) {
final int[] dp = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = coinKinds[0]; i <= amount; ++i) {
int min = Integer.MAX_VALUE - 1;
for (final int coinKind : coinKinds) {
if (i < coinKind) {
break;
}
final int remainAmount = i - coinKind;
if (min > dp[remainAmount]) {
min = dp[remainAmount];
}
}
dp[i] = min + 1;
}
for (int a = 0; a <= amount; ++a) {
final int minCount = dp[a];
if (minCount == Integer.MAX_VALUE) {
System.out.printf("For amount {}, there is no solution.%n", a);
continue;
}
System.out.printf("For amount %d, the minimum number of coins is %d.%n", a, minCount);
}
}
function changeCoin(coinKinds: number[], amount: number) {
const dp = new Array<number>(amount + 1).fill(Number.MAX_SAFE_INTEGER);
dp[0] = 0;
for (let i = coinKinds[0];i <= amount;i++) {
let min = Number.MAX_SAFE_INTEGER - 1;
for (const coinKind of coinKinds) {
if (i < coinKind) {
break;
}
const remainAmount = i - coinKind;
if (min > dp[remainAmount]) {
min = dp[remainAmount];
}
}
dp[i] = min + 1;
}
for (let a = 0;a <= amount;a++) {
const minCount = dp[a];
if (minCount === Number.MAX_SAFE_INTEGER) {
console.log(`For amount ${a}, there is no solution.`);
continue;
}
console.log(`For amount ${a}, the minimum number of coins is ${minCount}.`);
}
}
func ChangeCoin(coinKinds []int, amount int) {
const MAX_UNIT = ^uint(0)
const MAX_INT = int(MAX_UNIT >> 1)
dp := make([]int, amount+1)
for i := 0; i <= amount; i++ {
dp[i] = MAX_INT
}
dp[0] = 0
for i := coinKinds[0]; i <= amount; i++ {
min := MAX_INT - 1
for _, coinKind := range coinKinds {
if i < coinKind {
break
}
remainAmount := i - coinKind
if min > dp[remainAmount] {
min = dp[remainAmount]
}
}
dp[i] = min + 1
}
for a, minCount := range dp {
if minCount == MAX_INT {
fmt.Printf("For amount %d, there is no solution.\n", a)
continue
}
fmt.Printf("For amount %d, the minimum number of coins is %d.\n", a, minCount)
}
}
想要知道硬幣的組合方式，可以再添加一個長度為amount + 1的陣列，這個陣列裡面的元素都是長度為硬幣面額數量的陣列，且數值初始化為0，用來儲存湊到i元時，各種面額的硬幣的數量。程式碼如下：
pub fn change_coin(coin_kinds: &[usize], amount: usize) {
let coin_kinds_len = coin_kinds.len();
let mut dp = vec![usize::max_value(); amount + 1];
let mut coin_kinds_counts = vec![vec![0; coin_kinds_len]; amount + 1];
dp[0] = 0;
for i in coin_kinds[0]..=amount {
let mut min = usize::max_value() - 1;
for (c, coin_kind) in coin_kinds.iter().copied().enumerate() {
if i < coin_kind {
break;
}
let remain_amount = i - coin_kind;
if min > dp[remain_amount] {
min = dp[remain_amount];
unsafe {
copy_nonoverlapping(coin_kinds_counts[remain_amount].as_ptr(), coin_kinds_counts[i].as_mut_ptr(), coin_kinds_len);
}
coin_kinds_counts[i][c] += 1;
}
}
dp[i] = min + 1;
}
for (a, min_count) in dp.into_iter().enumerate() {
if min_count == usize::max_value() {
println!("For amount {}, there is no solution.", a);
continue;
}
println!("For amount {}, the minimum number of coins is {}. {:?}", a, min_count, coin_kinds_counts[a]);
}
}
public static void changeCoin(final int[] coinKinds, final int amount) {
final int coinKindsLen = coinKinds.length;
final int[] dp = new int[amount + 1];
final int[][] coinKindsCounts = new int[amount + 1][coinKindsLen];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = coinKinds[0]; i <= amount; ++i) {
int min = Integer.MAX_VALUE - 1;
for (int c = 0; c < coinKindsLen; ++c) {
final int coinKind = coinKinds[c];
if (i < coinKind) {
break;
}
final int remainAmount = i - coinKind;
if (min > dp[remainAmount]) {
min = dp[remainAmount];
System.arraycopy(coinKindsCounts[remainAmount], 0, coinKindsCounts[i], 0, coinKindsLen);
++coinKindsCounts[i][c];
}
}
dp[i] = min + 1;
}
for (int a = 0; a <= amount; ++a) {
final int minCount = dp[a];
if (minCount == Integer.MAX_VALUE) {
System.out.printf("For amount {}, there is no solution.%n", a);
continue;
}
System.out.printf("For amount %d, the minimum number of coins is %d. %s%n", a, minCount, Arrays.toString(coinKindsCounts[a]));
}
}
function changeCoin(coinKinds: number[], amount: number) {
const coinKindsLen = coinKinds.length;
const dp = new Array<number>(amount + 1).fill(Number.MAX_SAFE_INTEGER);
const coinKindsCounts = new Array<number[]>(amount + 1);
for (let i = 0;i <= amount;i++) {
coinKindsCounts[i] = new Array<number>(coinKindsLen).fill(0);
}
dp[0] = 0;
for (let i = coinKinds[0];i <= amount;i++) {
let min = Number.MAX_SAFE_INTEGER - 1;
for (let c = 0;c < coinKinds.length;c++) {
const coinKind = coinKinds[c];
if (i < coinKind) {
break;
}
const remainAmount = i - coinKind;
if (min > dp[remainAmount]) {
min = dp[remainAmount];
for (let k = 0;k < coinKindsLen;k++) {
coinKindsCounts[i][k] = coinKindsCounts[remainAmount][k];
}
coinKindsCounts[i][c] += 1;
}
}
dp[i] = min + 1;
}
for (let a = 0;a <= amount;a++) {
const minCount = dp[a];
if (minCount === Number.MAX_SAFE_INTEGER) {
console.log(`For amount ${a}, there is no solution.`);
continue;
}
console.log(`For amount ${a}, the minimum number of coins is ${minCount}. [${coinKindsCounts[a].join(", ")}]`);
}
}
func ChangeCoin(coinKinds []int, amount int) {
const MAX_UNIT = ^uint(0)
const MAX_INT = int(MAX_UNIT >> 1)
coinKindsLen := len(coinKinds)
amountInc := amount + 1
dp := make([]int, amountInc)
coinKindsCounts := make([][]int, amountInc)
for i := 0; i < amountInc; i++ {
dp[i] = MAX_INT
coinKindsCounts[i] = make([]int, coinKindsLen)
}
dp[0] = 0
for i := coinKinds[0]; i <= amount; i++ {
min := MAX_INT - 1
for c, coinKind := range coinKinds {
if i < coinKind {
break
}
remainAmount := i - coinKind
if min > dp[remainAmount] {
min = dp[remainAmount]
copy(coinKindsCounts[i], coinKindsCounts[remainAmount])
coinKindsCounts[i][c]++
}
}
dp[i] = min + 1
}
for a, minCount := range dp {
if minCount == MAX_INT {
fmt.Printf("For amount %d, there is no solution.\n", a)
continue
}
fmt.Printf("For amount %d, the minimum number of coins is %d. %s\n", a, minCount, strings.Replace(fmt.Sprint(coinKindsCounts[a]), " ", ", ", -1))
}
}
如果您覺得以上程式碼會吃掉太多記憶體空間，而且計算過程中還要在那邊複製陣列，看起來不是很好的話，其實也可以考慮只用長度為amount + 1的一維陣列，去記錄每個階段的問題在最佳解時最後拿到的硬幣面額(的索引值)。最後再反推回去就可以知道到底拿了哪些面額的硬幣了。
pub fn change_coin(coin_kinds: &[usize], amount: usize) {
let coin_kinds_len = coin_kinds.len();
let mut dp = vec![usize::max_value(); amount + 1];
let mut last_best_coin_kind_indexes = Vec::with_capacity(amount + 1);
unsafe {
last_best_coin_kind_indexes.set_len(amount + 1);
}
dp[0] = 0;
for i in coin_kinds[0]..=amount {
let mut min = usize::max_value() - 1;
for (c, coin_kind) in coin_kinds.iter().copied().enumerate() {
if i < coin_kind {
break;
}
let remain_amount = i - coin_kind;
if min > dp[remain_amount] {
min = dp[remain_amount];
last_best_coin_kind_indexes[i] = c;
}
}
dp[i] = min + 1;
}
for (a, min_count) in dp.into_iter().enumerate() {
if min_count == usize::max_value() {
println!("For amount {}, there is no solution.", a);
continue;
}
let mut coin_kinds_counts = vec![0; coin_kinds_len];
let mut n = a;
while n > 0 {
let last_best_coin_kind_index = last_best_coin_kind_indexes[n];
let last_best_coin_kind = coin_kinds[last_best_coin_kind_index];
coin_kinds_counts[last_best_coin_kind_index] += 1;
n -= last_best_coin_kind;
}
println!("For amount {}, the minimum number of coins is {}. {:?}", a, min_count, coin_kinds_counts);
}
}
public static void changeCoin(final int[] coinKinds, final int amount) {
final int coinKindsLen = coinKinds.length;
final int[] dp = new int[amount + 1];
final int[] lastBestCoinKindIndexes = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = coinKinds[0]; i <= amount; ++i) {
int min = Integer.MAX_VALUE - 1;
for (int c = 0; c < coinKindsLen; ++c) {
final int coinKind = coinKinds[c];
if (i < coinKind) {
break;
}
final int remainAmount = i - coinKind;
if (min > dp[remainAmount]) {
min = dp[remainAmount];
lastBestCoinKindIndexes[i] = c;
}
}
dp[i] = min + 1;
}
for (int a = 0; a <= amount; ++a) {
final int minCount = dp[a];
if (minCount == Integer.MAX_VALUE) {
System.out.printf("For amount {}, there is no solution.%n", a);
continue;
}
final int[] coinKindsCounts = new int[coinKindsLen];
int n = a;
while (n > 0) {
final int lastBestCoinKindIndex = lastBestCoinKindIndexes[n];
final int lastBestCoinKind = coinKinds[lastBestCoinKindIndex];
++coinKindsCounts[lastBestCoinKindIndex];
n -= lastBestCoinKind;
}
System.out.printf("For amount %d, the minimum number of coins is %d. %s%n", a, minCount, Arrays.toString(coinKindsCounts));
}
}
function changeCoin(coinKinds: number[], amount: number) {
const coinKindsLen = coinKinds.length;
const dp = new Array<number>(amount + 1).fill(Number.MAX_SAFE_INTEGER);
const lastBestCoinKindIndexes = new Array<number>(amount + 1);
dp[0] = 0;
for (let i = coinKinds[0];i <= amount;i++) {
let min = Number.MAX_SAFE_INTEGER - 1;
for (let c = 0;c < coinKinds.length;c++) {
const coinKind = coinKinds[c];
if (i < coinKind) {
break;
}
const remainAmount = i - coinKind;
if (min > dp[remainAmount]) {
min = dp[remainAmount];
lastBestCoinKindIndexes[i] = c;
}
}
dp[i] = min + 1;
}
for (let a = 0;a <= amount;a++) {
const minCount = dp[a];
if (minCount === Number.MAX_SAFE_INTEGER) {
console.log(`For amount ${a}, there is no solution.`);
continue;
}
const coinKindsCounts = new Array(coinKindsLen).fill(0);
let n = a;
while (n > 0) {
const lastBestCoinKindIndex = lastBestCoinKindIndexes[n];
const lastBestCoinKind = coinKinds[lastBestCoinKindIndex];
coinKindsCounts[lastBestCoinKindIndex] += 1;
n -= lastBestCoinKind;
}
console.log(`For amount ${a}, the minimum number of coins is ${minCount}. [${coinKindsCounts.join(", ")}]`);
}
}
func ChangeCoin(coinKinds []int, amount int) {
const MAX_UNIT = ^uint(0)
const MAX_INT = int(MAX_UNIT >> 1)
coinKindsLen := len(coinKinds)
amountInc := amount + 1
dp := make([]int, amountInc)
lastBestCoinKindIndexes := make([]int, amountInc)
for i := 0; i < amountInc; i++ {
dp[i] = MAX_INT
}
dp[0] = 0
for i := coinKinds[0]; i <= amount; i++ {
min := MAX_INT - 1
for c, coinKind := range coinKinds {
if i < coinKind {
break
}
remainAmount := i - coinKind
if min > dp[remainAmount] {
min = dp[remainAmount]
lastBestCoinKindIndexes[i] = c
}
}
dp[i] = min + 1
}
for a, minCount := range dp {
if minCount == MAX_INT {
fmt.Printf("For amount %d, there is no solution.\n", a)
continue
}
coinKindsCounts := make([]int, coinKindsLen)
n := a
for n > 0 {
lastBestCoinKindIndex := lastBestCoinKindIndexes[n]
lastBestCoinKind := coinKinds[lastBestCoinKindIndex]
coinKindsCounts[lastBestCoinKindIndex]++
n -= lastBestCoinKind
}
fmt.Printf("For amount %d, the minimum number of coins is %d. %s\n", a, minCount, strings.Replace(fmt.Sprint(coinKindsCounts), " ", ", ", -1))
}
}