溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹“動態規劃算法的問題有哪些”，在日常操作中，相信很多人在動態規劃算法的問題有哪些問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”動態規劃算法的問題有哪些”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！
問題： 給定數組arr，arr中的所有的值都為正數且不重復。每個值代表一種面值的貨幣，每種面值的貨幣可以使用任意張，再給定一個整數aim代表要找的錢數，求換錢有多少種方法。
若給定arr={5, 10, 25, 1}，aim=1000。
用0張5元的貨幣，讓[10, 25, 1]組成剩下的1000元，最終方法數記作------res1；
用1張5元的貨幣，讓[10, 25, 1]組成剩下的995元，最終方法數記作------res2；
用2張5元的貨幣，讓[10, 25, 1]組成剩下的990元，最終方法數記作------res3；
用3張5元的貨幣，讓[10, 25, 1]組成剩下的985元，最終方法數記作------res4；
……
用200張5元的貨幣，讓[10, 25, 1]組成剩下的0元，最終方法數記作------res201；
則res1、res2……res201的累加和即為最終的結果。
定義遞歸函數：int process1(arr, index, aim), 它的含義是如果用arr[index……N-1]這些面值的錢組成aim，返回總的方法數。
public static int coins1(int[] arr, int aim) {
long startTime = System.currentTimeMillis();
if (arr == null || arr.length == 0 || aim < 0) {
return 0;
}
int result = process1(arr,0,aim);
long endTime = System.currentTimeMillis();
System.out.println("暴力搜索方法所用時間：" + (endTime - startTime) +"ms");
return result;
}
public static int process1(int[] arr, int index, int aim) {
int res = 0;
// 判斷是否所有面值的貨幣均已經計算完
if (index == arr.length) {
// 判斷本次遞歸調用時錢的總數是否已經湊夠，如果已經湊夠則將總方法數加1
res = aim == 0 ? 1 : 0;
} else {
// 循環計算i張當前面值的貨幣
for (int i = 0; arr[index] * i <= aim; i++) {
// 遞歸調用當使用i張當前面值的貨幣時，用其它貨幣組成剩下的錢
res += process1(arr, index + 1, aim - arr[index] * i);
}
}
return res;
}暴力搜索方法比較好理解，但他在計算中存在大量的重復遞歸過程。 例如已經使用了0張5元和1張10元貨幣的情況下，后續將求： process1(arr,2,990) 而當計算使用2張5元和0張10元時，后續同樣需要求： process1(arr,2,990) 因此這種重復的遞歸運算將造成大量的時間浪費。
由于暴力搜索方法中存在大量的重復遞歸，因此我們可以使用一個“記憶庫”用于存儲已經計算過的值，在本題中，使用index貨幣組成剩下的aim錢的值是一一對應的，因此可以使用int mem[index][aim]數組表示記憶庫，其元素值為可以組成的方法數。
每計算完一個process(index,aim)，都將結果放入mem中，index和aim組成共同的key，返回結果為value。
要進入一個遞歸過程時，先以index和aim組成的key在mem中進行查詢，如果已經存在value，則直接使用，如果不存在，再進入遞歸過程。
public static int process2(int[] arr, int index, int aim, int[][] mem) {
int res = 0;
// 判斷是否所有面值的貨幣均已經計算完
if (index == arr.length) {
// 判斷本次遞歸調用時錢的總數是否已經湊夠，如果已經湊夠則將總方法數加1
res = aim == 0 ? 1 : 0;
} else {
int memVal = 0;
// 循環計算i張當前面值的貨幣
for (int i = 0; arr[index] * i <= aim; i++) {
// 獲取記憶庫中當使用i張index貨幣時，用其它貨幣組成剩下的錢
memVal = mem[index + 1][aim - arr[index] * i];
// 判斷記憶庫中存在記錄
if (memVal != 0) {
// 將記憶庫中的方法數累加到結果中
res += memVal == -1 ? 0 : memVal;
} else {
// 遞歸調用當使用i張當前面值的貨幣時，用其它貨幣組成剩下的錢
res += process2(arr, index + 1, aim - arr[index] * i, mem);
}
}
}
// 將使用index貨幣組成aim錢的結果存儲到記憶庫中
mem[index][aim] = res == 0 ? -1 : res;
return res;
}如果arr長度為N，生成行數為N，列數為aim+1的矩陣dp。 dp[i][j]的含義是在使用arr[0]...arr[i]貨幣的情況下，組成錢數j的方法數。
如果完全不用arr[i]貨幣，只使用arr[0]...arr[i-1]貨幣時，方法數為dp[i-1][j]。
如果用1張arr[i]貨幣，剩下的錢使用arr[0]...arr[i-1]貨幣組成，方法數為dp[i-1][j-1*arr[i]]。
如果用2張arr[i]貨幣，剩下的錢使用arr[0]...arr[i-1]貨幣組成，方法數為dp[i-1][j-1*arr[i]]。
如果用3張arr[i]貨幣，剩下的錢使用arr[0]...arr[i-1]貨幣組成，方法數為dp[i-1][j-1*arr[i]]。
……
dp[i][j]的值即為上述所有值得累加和。 求每一個位置都需要枚舉，時間復雜度為O(aim)。dp一共有N*aim個位置，所以總的時間復雜度為O(N*aim2) 最終的結果值即為矩陣最右下角的dp[N-1][aim]。
記憶化搜索方法就是某種形態的動態規劃方法。
記憶化搜索不關心到達某一個遞歸路徑的路程。只是單純地堆計算過的遞歸過程進行記錄，避免重復遞歸的過程。
動態規劃方法則是規定好每一個遞歸霍城的計算順序，一次進行計算，后面的計算過程嚴格依賴前面的計算過程。
兩者都是空間換時間的方法，也有枚舉的過程，區別在于動態規劃規定計算順序，而記憶搜索不用規定。
本質是利用申請的空間來記錄每一個暴力搜索的計算過程，下次要用結果的時候直接使用，而不再進行重復的遞歸過程。
動態規劃規定每一種遞歸狀態的計算順序，依次進行計算。從簡單到復雜，按順序計算。
public static int process3(int[] arr, int aim) {
// 創建dp矩陣
int[][] dp = new int[arr.length][aim + 1];
for (int i = 0; i < dp.length; i++) {
dp[i][0] = 1; // 湊成0元的方法必然是什么貨幣都不用，只有1種
if (i == 0) {
// 如果只是用arr[0]這一種貨幣，則能湊到j錢置1
for (int j = 0; j < dp[i].length; j++) {
dp[i][j] = j % arr[i] == 0 ? 1 : 0;
}
} else {
for (int j = 1; j < dp[i].length; j++) {
int temp = 0;
// 枚舉使用k張arr[i]貨幣后dp[i-1]中組成剩下錢數的方法數
for (int k = 0; k * arr[i] <= j; k++) {
temp += dp[i - 1][j - k * arr[i]];//方法數累加
}
dp[i][j] = temp;
}
}
}
// 返回dp矩陣最右下角的值即為最后結果
return dp[arr.length - 1][aim];
}由于動態規劃方法的執行順序有著嚴格的規定，因此使得對算法的進一步優化成為可能。 對于剛才的問題中，我們需要枚舉dp[i-1][j-k*arr[i]](k=1,2,3...)并與dp[i-1][j]累加，實際上dp[i-1][j-k*arr[i]](k=1,2,3...)的累加值就是dp[i][j-arr[i]]。
所以可以簡化為： dp[i][j] = dp[i][j-arr[i]] + dp[i-1][j] 從而徹底省略枚舉過程。時間復雜度從O(Naim2)變為O(Naim)
經過優化后的代碼實現如下：
public static int process4(int[] arr, int aim) {
// 創建dp矩陣
int[][] dp = new int[arr.length][aim + 1];
for (int i = 0; i < dp.length; i++) {
dp[i][0] = 1; // 湊成0元的方法必然是什么貨幣都不用，只有1種
for (int j = 1; j < dp[i].length; j++) {
if (i == 0) {
dp[i][j] = j % arr[i] == 0 ? 1 : 0;
} else if(j >= arr[i]){
dp[i][j] = dp[i][j - arr[i]] + dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
// 返回dp矩陣最右下角的值即為最后結果
return dp[arr.length - 1][aim];
}我們可以看到，經過優化的動態規劃方法速度已經非常讓人滿意，但是它的空間浪費卻很嚴重，我們發現動態規劃方法是嚴格的矩陣從上至下、從左至右的方向順序計算，那么其實真正每次計算式只需要用到的是當前行與當前行的上一行，因此其實我們可以將原本的dp二維矩陣簡化為一維向量。 通過讀取和修改向量本身的元素值來達到目的，修改后的代碼如下所示：
public static int process5(int[] arr, int aim) {
// 創建dp向量
int[] dp = new int[aim + 1];
for (int i = 0; i < arr.length; i++) {
dp[0] = 1; // 湊成0元的方法必然是什么貨幣都不用，只有1種
for (int j = 1; j < dp.length; j++) {
if (i == 0) {
dp[j] = j % arr[i] == 0 ? 1 : 0;
} else if(j >= arr[i]){
dp[j] += dp[j - arr[i]];
}
}
}
// 返回dp向量尾元素即最終結果
return dp[aim];
}上述所有的實現代碼中，都加入了記錄算法開始時間和結束時間的代碼，我們通過運行測試，得到下面的結果：
可以看到，暴力搜索方法毋庸置疑是速度最慢的，因為其存在大量的重復遞歸過程。
記憶化搜索方法由于避免了重復遞歸，因此效率更高一些。
經過優化的動態規劃方法可以看到在我的實測環境中，運行時間近乎為0ms，可以說是非常快的。
實現暴力遞歸方法；
在暴力搜索方法的函數中看看哪些參數可以代表遞歸過程。
找到代表遞歸過程的參數之后，記憶化搜索方法的實現非常容易。
通過分析記憶化搜索的依賴路徑，進而實現動態規劃。
根據記憶化搜索方法改出動態規劃方法，進而看看是否能夠化簡，如果能化簡，還能實現時間復雜度更低的動態規劃方法。
最優化原理：也就是最優子結構性質。指一個最優化策略具有這樣的性質，不論過去狀態和決策如何，對前面的決策所形成的狀態而言，余下的諸決策必須構成最優策略。簡單來說就是一個最優化策略的子策略總是最優的，如果一個問題滿足最優化原理，就成為其具有最優子結構性質。
無后效性：指某狀態下決策的收益，只與狀態和決策相關，與到達該狀態的路徑無關。
子問題的重疊性：動態規劃將原來具有指數級時間復雜度的暴力搜索算法改進成了具有多項式時間復雜度的算法。其中的關鍵在于解決冗余，這是動態規劃算法的根本目的。
到此，關于“動態規劃算法的問題有哪些”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
