動(dòng)態(tài)規(guī)劃算法的問題有哪些

這篇文章主要介紹“動(dòng)態(tài)規(guī)劃算法的問題有哪些”，在日常操作中，相信很多人在動(dòng)態(tài)規(guī)劃算法的問題有哪些問題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”動(dòng)態(tài)規(guī)劃算法的問題有哪些”的疑惑有所幫助！接下來，請(qǐng)跟著小編一起來學(xué)習(xí)吧！

問題： 給定數(shù)組arr，arr中的所有的值都為正數(shù)且不重復(fù)。每個(gè)值代表一種面值的貨幣，每種面值的貨幣可以使用任意張，再給定一個(gè)整數(shù)aim代表要找的錢數(shù)，求換錢有多少種方法。

暴力搜索方法

思路分析

若給定arr={5, 10, 25, 1}，aim=1000。

• 用0張5元的貨幣，讓[10, 25, 1]組成剩下的1000元，最終方法數(shù)記作------res1；

• 用1張5元的貨幣，讓[10, 25, 1]組成剩下的995元，最終方法數(shù)記作------res2；

• 用2張5元的貨幣，讓[10, 25, 1]組成剩下的990元，最終方法數(shù)記作------res3；

• 用3張5元的貨幣，讓[10, 25, 1]組成剩下的985元，最終方法數(shù)記作------res4；

• ……

• 用200張5元的貨幣，讓[10, 25, 1]組成剩下的0元，最終方法數(shù)記作------res201；

則res1、res2……res201的累加和即為最終的結(jié)果。

具體實(shí)現(xiàn)

定義遞歸函數(shù)：int process1(arr, index, aim), 它的含義是如果用arr[index……N-1]這些面值的錢組成aim，返回總的方法數(shù)。

        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("暴力搜索方法所用時(shí)間：" + (endTime - startTime) +"ms");
            return result;
        }
    
        public static int process1(int[] arr, int index, int aim) {
            int res = 0;
            // 判斷是否所有面值的貨幣均已經(jīng)計(jì)算完
            if (index == arr.length) {
                // 判斷本次遞歸調(diào)用時(shí)錢的總數(shù)是否已經(jīng)湊夠，如果已經(jīng)湊夠則將總方法數(shù)加1
                res = aim == 0 ? 1 : 0; 
            } else { 
                // 循環(huán)計(jì)算i張當(dāng)前面值的貨幣
                for (int i = 0; arr[index] * i <= aim; i++) {
                    // 遞歸調(diào)用當(dāng)使用i張當(dāng)前面值的貨幣時(shí)，用其它貨幣組成剩下的錢
                    res += process1(arr, index + 1, aim - arr[index] * i);
                }
            }
            return res;
        }

暴力搜索方法比較好理解，但他在計(jì)算中存在大量的重復(fù)遞歸過程。 例如已經(jīng)使用了0張5元和1張10元貨幣的情況下，后續(xù)將求： process1(arr,2,990) 而當(dāng)計(jì)算使用2張5元和0張10元時(shí)，后續(xù)同樣需要求： process1(arr,2,990) 因此這種重復(fù)的遞歸運(yùn)算將造成大量的時(shí)間浪費(fèi)。

記憶搜索方法

思路分析

由于暴力搜索方法中存在大量的重復(fù)遞歸，因此我們可以使用一個(gè)“記憶庫”用于存儲(chǔ)已經(jīng)計(jì)算過的值，在本題中，使用index貨幣組成剩下的aim錢的值是一一對(duì)應(yīng)的，因此可以使用int mem[index][aim]數(shù)組表示記憶庫，其元素值為可以組成的方法數(shù)。

具體實(shí)現(xiàn)

• 每計(jì)算完一個(gè)process(index,aim)，都將結(jié)果放入mem中，index和aim組成共同的key，返回結(jié)果為value。

• 要進(jìn)入一個(gè)遞歸過程時(shí)，先以index和aim組成的key在mem中進(jìn)行查詢，如果已經(jīng)存在value，則直接使用，如果不存在，再進(jìn)入遞歸過程。

        public static int process2(int[] arr, int index, int aim, int[][] mem) {
            int res = 0;
            // 判斷是否所有面值的貨幣均已經(jīng)計(jì)算完
            if (index == arr.length) {
                // 判斷本次遞歸調(diào)用時(shí)錢的總數(shù)是否已經(jīng)湊夠，如果已經(jīng)湊夠則將總方法數(shù)加1
                res = aim == 0 ? 1 : 0;
            } else {
                int memVal = 0;
                // 循環(huán)計(jì)算i張當(dāng)前面值的貨幣
                for (int i = 0; arr[index] * i <= aim; i++) {
                    // 獲取記憶庫中當(dāng)使用i張index貨幣時(shí)，用其它貨幣組成剩下的錢
                    memVal = mem[index + 1][aim - arr[index] * i];
                    // 判斷記憶庫中存在記錄
                    if (memVal != 0) {
                        // 將記憶庫中的方法數(shù)累加到結(jié)果中
                        res += memVal == -1 ? 0 : memVal;
                    } else {
                        // 遞歸調(diào)用當(dāng)使用i張當(dāng)前面值的貨幣時(shí)，用其它貨幣組成剩下的錢
                        res += process2(arr, index + 1, aim - arr[index] * i, mem);
                    }
                }
            }
            // 將使用index貨幣組成aim錢的結(jié)果存儲(chǔ)到記憶庫中
            mem[index][aim] = res == 0 ? -1 : res;
            return res;
        }

動(dòng)態(tài)規(guī)劃方法

思路分析

如果arr長(zhǎng)度為N，生成行數(shù)為N，列數(shù)為aim+1的矩陣dp。 dp[i][j]的含義是在使用arr[0]...arr[i]貨幣的情況下，組成錢數(shù)j的方法數(shù)。

1. 如果完全不用arr[i]貨幣，只使用arr[0]...arr[i-1]貨幣時(shí)，方法數(shù)為dp[i-1][j]。

2. 如果用1張arr[i]貨幣，剩下的錢使用arr[0]...arr[i-1]貨幣組成，方法數(shù)為dp[i-1][j-1*arr[i]]。

3. 如果用2張arr[i]貨幣，剩下的錢使用arr[0]...arr[i-1]貨幣組成，方法數(shù)為dp[i-1][j-1*arr[i]]。

4. 如果用3張arr[i]貨幣，剩下的錢使用arr[0]...arr[i-1]貨幣組成，方法數(shù)為dp[i-1][j-1*arr[i]]。

5. ……

dp[i][j]的值即為上述所有值得累加和。 求每一個(gè)位置都需要枚舉，時(shí)間復(fù)雜度為O(aim)。dp一共有N*aim個(gè)位置，所以總的時(shí)間復(fù)雜度為O(N*aim2) 最終的結(jié)果值即為矩陣最右下角的dp[N-1][aim]。

記憶搜索方法與動(dòng)態(tài)規(guī)劃方法的聯(lián)系

• 記憶化搜索方法就是某種形態(tài)的動(dòng)態(tài)規(guī)劃方法。

• 記憶化搜索不關(guān)心到達(dá)某一個(gè)遞歸路徑的路程。只是單純地堆計(jì)算過的遞歸過程進(jìn)行記錄，避免重復(fù)遞歸的過程。

• 動(dòng)態(tài)規(guī)劃方法則是規(guī)定好每一個(gè)遞歸霍城的計(jì)算順序，一次進(jìn)行計(jì)算，后面的計(jì)算過程嚴(yán)格依賴前面的計(jì)算過程。

• 兩者都是空間換時(shí)間的方法，也有枚舉的過程，區(qū)別在于動(dòng)態(tài)規(guī)劃規(guī)定計(jì)算順序，而記憶搜索不用規(guī)定。

什么是動(dòng)態(tài)規(guī)劃方法

• 本質(zhì)是利用申請(qǐng)的空間來記錄每一個(gè)暴力搜索的計(jì)算過程，下次要用結(jié)果的時(shí)候直接使用，而不再進(jìn)行重復(fù)的遞歸過程。

• 動(dòng)態(tài)規(guī)劃規(guī)定每一種遞歸狀態(tài)的計(jì)算順序，依次進(jìn)行計(jì)算。從簡(jiǎn)單到復(fù)雜，按順序計(jì)算。

具體實(shí)現(xiàn)

        public static int process3(int[] arr, int aim) {
            // 創(chuàng)建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(luò)錢置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]中組成剩下錢數(shù)的方法數(shù)
                        for (int k = 0; k * arr[i] <= j; k++) {
                            temp += dp[i - 1][j - k * arr[i]];//方法數(shù)累加
                        }
                        dp[i][j] = temp;
                    }
                }
            }
            // 返回dp矩陣最右下角的值即為最后結(jié)果
            return dp[arr.length - 1][aim];
        }

動(dòng)態(tài)規(guī)劃方法的再優(yōu)化

思路分析

由于動(dòng)態(tài)規(guī)劃方法的執(zhí)行順序有著嚴(yán)格的規(guī)定，因此使得對(duì)算法的進(jìn)一步優(yōu)化成為可能。 對(duì)于剛才的問題中，我們需要枚舉dp[i-1][j-k*arr[i]](k=1,2,3...)并與dp[i-1][j]累加，實(shí)際上dp[i-1][j-k*arr[i]](k=1,2,3...)的累加值就是dp[i][j-arr[i]]。

所以可以簡(jiǎn)化為： dp[i][j] = dp[i][j-arr[i]] + dp[i-1][j] 從而徹底省略枚舉過程。時(shí)間復(fù)雜度從O(Naim2)變?yōu)镺(Naim)

具體實(shí)現(xiàn)

經(jīng)過優(yōu)化后的代碼實(shí)現(xiàn)如下：

        public static int process4(int[] arr, int aim) {
            // 創(chuàng)建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矩陣最右下角的值即為最后結(jié)果
            return dp[arr.length - 1][aim];
        }

動(dòng)態(tài)規(guī)劃方法的空間優(yōu)化

我們可以看到，經(jīng)過優(yōu)化的動(dòng)態(tài)規(guī)劃方法速度已經(jīng)非常讓人滿意，但是它的空間浪費(fèi)卻很嚴(yán)重，我們發(fā)現(xiàn)動(dòng)態(tài)規(guī)劃方法是嚴(yán)格的矩陣從上至下、從左至右的方向順序計(jì)算，那么其實(shí)真正每次計(jì)算式只需要用到的是當(dāng)前行與當(dāng)前行的上一行，因此其實(shí)我們可以將原本的dp二維矩陣簡(jiǎn)化為一維向量。 通過讀取和修改向量本身的元素值來達(dá)到目的，修改后的代碼如下所示：

        public static int process5(int[] arr, int aim) {
            // 創(chuàng)建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向量尾元素即最終結(jié)果
            return dp[aim];
        }

各種計(jì)算方法的運(yùn)行速度對(duì)比

上述所有的實(shí)現(xiàn)代碼中，都加入了記錄算法開始時(shí)間和結(jié)束時(shí)間的代碼，我們通過運(yùn)行測(cè)試，得到下面的結(jié)果：

• 可以看到，暴力搜索方法毋庸置疑是速度最慢的，因?yàn)槠浯嬖诖罅康闹貜?fù)遞歸過程。

• 記憶化搜索方法由于避免了重復(fù)遞歸，因此效率更高一些。

• 經(jīng)過優(yōu)化的動(dòng)態(tài)規(guī)劃方法可以看到在我的實(shí)測(cè)環(huán)境中，運(yùn)行時(shí)間近乎為0ms，可以說是非?？斓摹?/p>

暴力遞歸優(yōu)化成動(dòng)態(tài)規(guī)劃方法的大體過程

1. 實(shí)現(xiàn)暴力遞歸方法；

2. 在暴力搜索方法的函數(shù)中看看哪些參數(shù)可以代表遞歸過程。

3. 找到代表遞歸過程的參數(shù)之后，記憶化搜索方法的實(shí)現(xiàn)非常容易。

4. 通過分析記憶化搜索的依賴路徑，進(jìn)而實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃。

5. 根據(jù)記憶化搜索方法改出動(dòng)態(tài)規(guī)劃方法，進(jìn)而看看是否能夠化簡(jiǎn)，如果能化簡(jiǎn)，還能實(shí)現(xiàn)時(shí)間復(fù)雜度更低的動(dòng)態(tài)規(guī)劃方法。

動(dòng)態(tài)規(guī)劃方法的關(guān)鍵點(diǎn)

1. 最優(yōu)化原理：也就是最優(yōu)子結(jié)構(gòu)性質(zhì)。指一個(gè)最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡(jiǎn)單來說就是一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的，如果一個(gè)問題滿足最優(yōu)化原理，就成為其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

2. 無后效性：指某狀態(tài)下決策的收益，只與狀態(tài)和決策相關(guān)，與到達(dá)該狀態(tài)的路徑無關(guān)。

3. 子問題的重疊性：動(dòng)態(tài)規(guī)劃將原來具有指數(shù)級(jí)時(shí)間復(fù)雜度的暴力搜索算法改進(jìn)成了具有多項(xiàng)式時(shí)間復(fù)雜度的算法。其中的關(guān)鍵在于解決冗余，這是動(dòng)態(tài)規(guī)劃算法的根本目的。

到此，關(guān)于“動(dòng)態(tài)規(guī)劃算法的問題有哪些”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！