未分類

Coin Change

DynamicProgramming, Go, LeetCode

Coin Change

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:

1
2
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:

1
2
coins = [2], amount = 3
return -1.

Note:

You may assume that you have an infinite number of each kind of coin.

提示 解題應用
DynamicProgramming Recursive

Default:

1
2
3
func coinChange(coins []int, amount int) int {
}

解答思路:

非常典型的Dynamic Programming題目，一開始只用遞回的方式來做排列組合試著找出符合條件的結果，不出所料後面越長的測資組合越容易導致超時，所以還需要在利用空間換取時間，初始化陣列來紀錄一路上出現值的最小組合數，並由後續加以重覆使用以節省時間，直到全數組合均遍歷完畢才向上回傳最小組合數。

程式碼解說:

一開始便將參數帶入遞回函數之中，其中第三個參數陣列用來紀錄一路上出現值的最小組合數，index代表出現的值，而value則是表示其值的組合數，當然也可以使用hashmap來儲存，不過考量到測資組合有1出現，還是使用一連續空間會比較佳(當然浪費的空間也相當多)

1
2
3
func coinChange(coins []int, amount int) int {
	return combine(coins, amount, make([]int, amount+1))
}

接下來就是處理遞回的細節，需要的金額為0的話便回傳0，如果金額為負數便回傳-1(表示無法組合出來)，而如果該金額剛好先前曾找出最小組合數(不為0)便直接回傳，上述都不符合的話就用迴圈取出所有硬幣面額做組合並再次向下遞回，同時從每次的回傳中找出最小值(初始值為int的32位元極大值，且最小組合數不得為-1)，如果最後最小值不為極大值，便紀錄該出現值的最小組合數，否則將該值的組合數紀錄為-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func combine(coins []int, amount int, num []int) int {
	var tmp int
	if amount == 0 {
		return 0
	} else if amount < 0 {
		return -1
	} else if num[amount] != 0 {
		return num[amount]
	}
	min := math.MaxInt32
	for _, v := range coins {
		tmp = combine(coins, amount-v, num)
		if tmp != -1 && tmp < min {
			min = tmp + 1
		}
	}
	if min == math.MaxInt32 {
		num[amount] = -1
	} else {
		num[amount] = min
	}
	return num[amount]
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func coinChange(coins []int, amount int) int {
	return combine(coins, amount, make([]int, amount+1))
}
func combine(coins []int, amount int, num []int) int {
	var tmp int
	if amount == 0 {
		return 0
	} else if amount < 0 {
		return -1
	} else if num[amount] != 0 {
		return num[amount]
	}
	min := math.MaxInt32
	for _, v := range coins {
		tmp = combine(coins, amount-v, num)
		if tmp != -1 && tmp < min {
			min = tmp + 1
		}
	}
	if min == math.MaxInt32 {
		num[amount] = -1
	} else {
		num[amount] = min
	}
	return num[amount]
}

總結:

給予數個硬幣的面額值，利用最少的硬幣數組出符合目標條件的金額，一開始只用遞回的方式來做排列組合，並利用空間換取時間初始化陣列來紀錄一路上出現值的最小組合數，並由後續加以重覆使用以節省時間，直到全數組合均遍歷完畢才向上回傳最小組合數。

分享到