溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
動態規劃的基本思想是將待求解問題分解成若干個子問題，先求解子問題，并將這些子問題的解保存起來，如果以后在求解較大子問題的時候需要用到這些子問題的解，就可以直接取出這些已經計算過的解而免去重復運算。保存子問題的解可以使用填表方式，例如保存在數組中。
用一個實際例子來體現動態規劃的算法思想——硬幣找零問題。
問題描述:
假設有幾種硬幣，并且數量無限。請找出能夠組成某個數目的找零所使用最少的硬幣數。例如幾種硬幣為[1, 3, 5], 面值2的最少硬幣數為2(1, 1), 面值4的最少硬幣數為2(1, 3), 面值11的最少硬幣數為3(5, 5, 1或者5, 3, 3).
問題分析:
假設不同的幾組硬幣為數組coin[0, ..., n-1]. 則求面值k的最少硬幣數count(k), 那么count函數和硬幣數組coin滿足這樣一個條件:
count(k) = min(count(k - coin[0]), ..., count(k - coin[n - 1])) + 1;
并且在符合條件k - coin[i] >= 0 && k - coin[i] < k的情況下, 前面的公式才成立.
因為k - coin[i] < k的緣故, 那么在求count(k)時, 必須滿足count(i)(i <- [0, k-1])已知, 所以這里又涉及到回溯的問題.
所以我們可以創建一個矩陣matrix[k + 1][coin.length + 1], 使matrix[0][j]全部初始化為0值, 而在matrix[i][coin.length]保存面值為i的最少硬幣數.
而且具體的過程如下:
* 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代碼實現如下:
public static int backTrackingCoin(int[] coins, int k) {//回溯法+動態規劃
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時, preK才能存在于數組matrix中, 才能夠進行回溯.
matrix[i][j] = matrix[preK][coins.length] + 1;//面值i在進行回溯
if (matrix[i][coins.length] == 0 || matrix[i][j] < matrix[i][coins.length]) {//如果當前的硬幣數目是最少的, 更新min列的最少硬幣數目
matrix[i][coins.length] = matrix[i][j];
}
}
}
}
return matrix[k][coins.length];
}
代碼經過測試, 題目給出的測試用例全部通過!
總結
以上就是本文關于Java動態規劃之硬幣找零問題實現代碼的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題。如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
