動(dòng)態(tài)規(guī)劃的基本思想是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，并將這些子問(wèn)題的解保存起來(lái)，如果以后在求解較大子問(wèn)題的時(shí)候需要用到這些子問(wèn)題的解，就可以直接取出這些已經(jīng)計(jì)算過(guò)的解而免去重復(fù)運(yùn)算。保存子問(wèn)題的解可以使用填表方式，例如保存在數(shù)組中。
用一個(gè)實(shí)際例子來(lái)體現(xiàn)動(dòng)態(tài)規(guī)劃的算法思想——硬幣找零問(wèn)題。
問(wèn)題描述:
假設(shè)有幾種硬幣，并且數(shù)量無(wú)限。請(qǐng)找出能夠組成某個(gè)數(shù)目的找零所使用最少的硬幣數(shù)。例如幾種硬幣為[1, 3, 5], 面值2的最少硬幣數(shù)為2(1, 1), 面值4的最少硬幣數(shù)為2(1, 3), 面值11的最少硬幣數(shù)為3(5, 5, 1或者5, 3, 3).
問(wèn)題分析:
假設(shè)不同的幾組硬幣為數(shù)組coin[0, ..., n-1]. 則求面值k的最少硬幣數(shù)count(k), 那么count函數(shù)和硬幣數(shù)組coin滿(mǎn)足這樣一個(gè)條件:
count(k) = min(count(k - coin[0]), ..., count(k - coin[n - 1])) + 1;
并且在符合條件k - coin[i] >= 0 && k - coin[i] < k的情況下, 前面的公式才成立.
因?yàn)閗 - coin[i] < k的緣故, 那么在求count(k)時(shí), 必須滿(mǎn)足count(i)(i <- [0, k-1])已知, 所以這里又涉及到回溯的問(wèn)題.
所以我們可以創(chuàng)建一個(gè)矩陣matrix[k + 1][coin.length + 1], 使matrix[0][j]全部初始化為0值, 而在matrix[i][coin.length]保存面值為i的最少硬幣數(shù).
而且具體的過(guò)程如下:
|
1
2
3
4
5
6
7
8
9
|
* k|coin 1 3 5 min * 0 0 0 0 0 * 1 1 0 0 1 * 2 2 0 0 2 * 3 3 1 0 3, 1 * 4 2 2 0 2, 2 * 5 3 3 1 3, 3, 1 * 6 2 2 2 2, 2, 2 * ... |
最后, 具體的Java代碼實(shí)現(xiàn)如下:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public static int backTrackingCoin(int[] coins, int k) {//回溯法+動(dòng)態(tài)規(guī)劃 if (coins == null || coins.length == 0 || k < 1) { return 0; } int[][] matrix = new int[k + 1][coins.length + 1]; for (int i = 1; i <= k; i++) { for (int j = 0; j < coins.length; j++) { int preK = i - coins[j]; if (preK > -1) {//只有在不小于0時(shí), preK才能存在于數(shù)組matrix中, 才能夠進(jìn)行回溯. matrix[i][j] = matrix[preK][coins.length] + 1;//面值i在進(jìn)行回溯 if (matrix[i][coins.length] == 0 || matrix[i][j] < matrix[i][coins.length]) {//如果當(dāng)前的硬幣數(shù)目是最少的, 更新min列的最少硬幣數(shù)目 matrix[i][coins.length] = matrix[i][j]; } } } } return matrix[k][coins.length]; } |
代碼經(jīng)過(guò)測(cè)試, 題目給出的測(cè)試用例全部通過(guò)!
總結(jié)
以上就是本文關(guān)于Java動(dòng)態(tài)規(guī)劃之硬幣找零問(wèn)題實(shí)現(xiàn)代碼的全部?jī)?nèi)容，希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專(zhuān)題。如有不足之處，歡迎留言指出。感謝朋友們對(duì)本站的支持！
原文鏈接：http://www.cnblogs.com/littlepanpc/p/7857599.html
