Java算法之動(dòng)態(tài)規(guī)劃

前言

? 最近這一段時(shí)間一直在刷算法題，基本上一有時(shí)間就會(huì)做一兩道，這兩天做了幾道動(dòng)態(tài)規(guī)劃的問(wèn)題，動(dòng)態(tài)規(guī)劃之前一直是我比較頭疼的一個(gè)問(wèn)題，感覺(jué)好復(fù)雜，一遇到這樣的問(wèn)題就想跳過(guò)，昨天耐著性子做了一道動(dòng)態(tài)規(guī)劃的題，感覺(jué)沒(méi)有我想象的那么難，無(wú)非就是先定義dp數(shù)組，然后找到初始值，再寫(xiě)出狀態(tài)轉(zhuǎn)移方程，一步一步來(lái)，難點(diǎn)就是如何確定一個(gè)正確的狀態(tài)，這是一個(gè)一直困擾我的問(wèn)題，而且在寫(xiě)狀態(tài)方程時(shí)要細(xì)心一點(diǎn)，不要出現(xiàn)錯(cuò)誤，這篇文章就是記錄一下自己的學(xué)習(xí)體會(huì)和心得。

動(dòng)態(tài)規(guī)劃的基本概念

? 動(dòng)態(tài)規(guī)劃（Dynamic Programming，簡(jiǎn)稱DP）是一種在數(shù)學(xué)、計(jì)算機(jī)科學(xué)和經(jīng)濟(jì)學(xué)中使用的，通過(guò)把原問(wèn)題分解為相對(duì)簡(jiǎn)單的子問(wèn)題的方式來(lái)求解復(fù)雜問(wèn)題的方法。動(dòng)態(tài)規(guī)劃常常適用于有重疊子問(wèn)題和最優(yōu)子結(jié)構(gòu)特性的問(wèn)題。

? 動(dòng)態(tài)規(guī)劃的基本思想是，將待求解的問(wèn)題分解成若干個(gè)相互聯(lián)系的子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。動(dòng)態(tài)規(guī)劃的關(guān)鍵在于正確地定義子問(wèn)題，以及子問(wèn)題的解如何推導(dǎo)出原問(wèn)題的解。

? 動(dòng)態(tài)規(guī)劃通常用于求解具有最優(yōu)子結(jié)構(gòu)特性的問(wèn)題，即問(wèn)題的最優(yōu)解可以由其子問(wèn)題的最優(yōu)解有效地構(gòu)造出來(lái)。此外，動(dòng)態(tài)規(guī)劃還要求子問(wèn)題空間必須足夠小，即子問(wèn)題的數(shù)量隨著問(wèn)題規(guī)模的增加不會(huì)增長(zhǎng)得太快，以便能夠用有限的內(nèi)存和時(shí)間來(lái)解決。

貪心算法

? 在這里我想提一下貪心算法，為什么要提一下貪心算法呢，因?yàn)槲矣X(jué)得這兩個(gè)算法之間存在一些共同點(diǎn)。貪心算法（Greedy Algorithm）是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)（即最有利）的選擇，從而希望導(dǎo)致結(jié)果是全局最好或最優(yōu)的算法。這和動(dòng)態(tài)規(guī)劃的將問(wèn)題分解為若干個(gè)子問(wèn)題求解有些類似，都是從每一個(gè)小問(wèn)題出發(fā)，然后慢慢擴(kuò)展到最后的原問(wèn)題，這兩個(gè)算法在最優(yōu)子結(jié)構(gòu)特性的問(wèn)題解決上都尤為有效，貪心算法的優(yōu)點(diǎn)是簡(jiǎn)單、直觀且運(yùn)行速度快，因?yàn)槊恳徊街魂P(guān)注當(dāng)前狀態(tài)下的最優(yōu)選擇，而不考慮未來(lái)可能的變化。但是，如果問(wèn)題不滿足貪心選擇性質(zhì)，貪心算法就無(wú)法保證得到全局最優(yōu)解。在這種情況下，可能需要使用其他方法，如動(dòng)態(tài)規(guī)劃。

? 先舉一個(gè)貪心算法的小例子，比如找零問(wèn)題就是一個(gè)典型的貪心算法應(yīng)用。假設(shè)有面值為1元、2元、5元、10元、20元、50元、100元的紙幣，目標(biāo)是找出一個(gè)給定金額的最少紙幣數(shù)。貪心策略是每次盡可能選擇面值最大的紙幣，因?yàn)檫@樣可以減少紙幣的數(shù)量。

? 再舉一個(gè)不滿足貪心選擇的性質(zhì)，比如貪心算法的一個(gè)經(jīng)典案例，背包問(wèn)題，背包問(wèn)題有一個(gè)背包，背包容量是M=150。有7個(gè)物品，物品可以分割成任意大小。要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過(guò)總?cè)萘?。那么運(yùn)用貪心算法的思想，先求出每種物品的單位價(jià)值，再?gòu)淖钪靛X(qián)的開(kāi)始裝，直到背包裝滿為止。但如果對(duì)這道題修改一下，不能分割物品，那此時(shí)貪心算法就會(huì)失效，這就是0-1背包問(wèn)題。此時(shí)，需要用動(dòng)態(tài)規(guī)劃來(lái)解決。

幾道例題

1.0-1背包問(wèn)題

?

public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//輸入商場(chǎng)物品的數(shù)量int N = scan.nextInt();//輸入小明的背包容量int V = scan.nextInt();//定義兩個(gè)數(shù)組分別記錄商品的重量和價(jià)格int[] weight = new int[N];int[] value = new int[N];for (int i = 0; i < N; i++) {//重量weight[i] = scan.nextInt();//價(jià)值value[i] = scan.nextInt();}//設(shè)置dp表int[][] dp = new int[N+1][V+1];//循環(huán)遍歷每一個(gè)商品，每次循環(huán)都要得出在背包容量為1-->V的每種情況下，他所含的價(jià)值for (int j = 1;j<=N;j++){//從背包容量為1時(shí)開(kāi)始遍歷for(int k = 1;k<=V;k++){//如果商品容量大于背包容量，那么就裝不進(jìn)去，那么總價(jià)值就為前一個(gè)商品在這個(gè)容量的總價(jià)值if(weight[j-1]>k){dp[j][k] = dp[j-1][k];}//否則，比較放入當(dāng)前物品和不放入當(dāng)前物品哪種情況價(jià)值更高else{//dp[j-1][k-weight[j-1]]這個(gè)代碼是為了求減去當(dāng)前商品的容量后，背包的總價(jià)值，再加上此時(shí)加入這個(gè)商品后的價(jià)值，得到一個(gè)新的總價(jià)值，如果這個(gè)總價(jià)值大于相同容量下前一個(gè)商品的價(jià)值，那么就值得放入，否則不值得放入dp[j][k] = Math.max(dp[j-1][k-weight[j-1]]+value[j-1],dp[j-1][k]);}}}System.out.println(dp[N][V]);scan.close();}
}

2.爬樓梯

? 題目描述：假設(shè)你現(xiàn)在正在爬樓梯。需要n階你才能到達(dá)樓頂。每次你可以爬1或者2個(gè)臺(tái)階，一共有多少種方法可以到達(dá)樓頂？

? 那么對(duì)于這題，很明顯我們可以使用動(dòng)態(tài)規(guī)劃來(lái)進(jìn)行求解，狀態(tài)很好確定，首先確立邊界，當(dāng)爬一層有多少方法，當(dāng)爬兩層有多少種方法，那么設(shè)立狀態(tài)轉(zhuǎn)移方程，當(dāng)爬第n階時(shí)，有兩種狀態(tài)，要么現(xiàn)在處于第n-1個(gè)階梯，要么現(xiàn)在處于第n-2個(gè)階梯，那爬第n階的方法總數(shù)就是爬n-1個(gè)階梯的方法數(shù)加上爬n-2個(gè)階梯的方法數(shù)。

class Solution {public int climbStairs(int n) {//當(dāng)n為1時(shí)直接返回1，這里返回是因?yàn)楹竺鎑p數(shù)組長(zhǎng)度為n+1，如果n為1，那后面對(duì)dp[2]賦值就會(huì)出現(xiàn)溢出if(n == 1){return 1;}    //設(shè)置dp數(shù)組，表示爬第n階臺(tái)階的方法數(shù)   int [] dp = new int[n+1];//爬第1階臺(tái)階的方法數(shù)dp[1] = 1;//爬第2階臺(tái)階的方法數(shù)dp[2] = 2;//從第三階開(kāi)始循環(huán)遍歷for(int i = 3;i < n+1;i++){//狀態(tài)轉(zhuǎn)移方程dp[i] = dp[i-2] + dp[i-1];}//返回return dp[n];}}

3.買股票的最佳時(shí)機(jī)

? 在練習(xí)數(shù)組的相關(guān)算法題時(shí)，有過(guò)一道買賣股票的題，但這兩個(gè)題不太一樣，但都是用動(dòng)態(tài)規(guī)劃來(lái)解決的，這道題要求是只能買賣一次，那根據(jù)動(dòng)態(tài)規(guī)劃的思想，每天都有兩種狀態(tài)，一種是手里沒(méi)有股票，一種是手里有股票，那可以設(shè)置兩個(gè)邊界，一個(gè)是第一天手里沒(méi)有股票的利潤(rùn)，一種是手里有股票的利潤(rùn)，然后遞推下一個(gè)，根據(jù)題目我們知道只能買賣一次，那么如果這一天手里有股票，那可能是前面買的，也可能是今天買的，有這兩種情況，比較兩種的較大者作為當(dāng)天有股票的最大利潤(rùn)。

? 如果當(dāng)天手里沒(méi)有股票，那可能是前面賣的，也可能是當(dāng)天賣的，同樣，我們比較兩者的較大值作為當(dāng)天的最大利潤(rùn)。

class Solution {public int maxProfit(int[] prices) {if (prices == null || prices.length == 0)return 0;int length = prices.length;int[][] dp = new int[length][2];//邊界條件dp[0][0]= 0;dp[0][1] = -prices[0];for (int i = 1; i < length; i++) {//遞推公式dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);}//毋庸置疑，最后肯定是手里沒(méi)持有股票利潤(rùn)才會(huì)最大，也就是賣出去了return dp[length - 1][0];
}
}

4.最大子序和

? 看到這道題后，感覺(jué)沒(méi)有什么思路，后來(lái)去問(wèn)了一下ai，感覺(jué)茅塞頓開(kāi)，基本思路是定義一個(gè)dp數(shù)組，這個(gè)dp數(shù)組所記錄的就是以當(dāng)前索引為右邊界時(shí)，這時(shí)候的最大子數(shù)組，那么遞推公式就是dp[i] = nums[i] + Math.max(dp[i-1],0)，為什么要有這個(gè)代碼呢Math.max(dp[i-1],0)，這段代碼是比較dp[i-1]是否大于0，如果小于零，那么就不能再加了，因?yàn)闀?huì)越加越小，此時(shí)從當(dāng)前索引重新開(kāi)始記錄，為什么會(huì)越加越小呢，我當(dāng)時(shí)的疑問(wèn)是，如果當(dāng)前索引是一個(gè)正數(shù)，那不仍然會(huì)變大嗎，怎么會(huì)是越加越小呢，我思索了一會(huì)，想明白了，以當(dāng)前索引的數(shù)據(jù)來(lái)看，如果加上一個(gè)負(fù)數(shù)，那就會(huì)變小，不如直接舍棄，重新開(kāi)始記錄，至于當(dāng)前索引是正數(shù)還是負(fù)數(shù)，這個(gè)不用考慮，因?yàn)闊o(wú)論是正數(shù)還是負(fù)數(shù)，加上一個(gè)負(fù)數(shù)都會(huì)變小。max = Math.max(dp[i],max);，這里則是記錄最大值，每次循環(huán)都更新max的值，最后返回max。

class Solution {public int maxSubArray(int[] nums) {int length = nums.length;int [] dp = new int [length];dp[0] = nums[0];int max = dp[0];for(int i = 1;i<length;i++){dp[i] = nums[i] + Math.max(dp[i-1],0);max = Math.max(dp[i],max);}return max;}
}

5.打家劫舍

? 這道題也比較簡(jiǎn)單，好理解，定義一個(gè)dp數(shù)組，如果不搶這一家，那能獲取的利潤(rùn)有兩種情況，一種是搶了前一家，另一種是沒(méi)搶前一家，比較這兩種的最大值，如果搶了這一家，那就只有一種情況，沒(méi)搶前一家的最大利潤(rùn)。

class Solution {public int rob(int[] nums) {int length = nums.length;if(length == 1){return nums[0];}//定義dp數(shù)組int[][] dp = new int [length][2];//不搶第一家的利潤(rùn)dp[0][0] = 0;//搶了第一家的利潤(rùn)dp[0][1] = nums[0];int max = 0;int mid = 0;for(int i = 1;i<length;i++){dp[i][0] = Math.max(dp[i-1][1],dp[i-1][0]);dp[i][1] = dp[i-1][0]+nums[i];//mid用于比較搶和不搶那種利潤(rùn)最大mid = Math.max(dp[i][0],dp[i][1]);max = Math.max(max,mid);}return max;}
}

6.蝸牛

? 這是一道去年藍(lán)橋杯省賽B組的真題，那么解題思路如下

? 首先，還是定義dp數(shù)組，那狀態(tài)如何確立，確立狀態(tài)就是看有幾種選擇，那么由題可知，蝸牛移動(dòng)有兩種方式，一種是直接爬過(guò)去，一種是通過(guò)傳送門(mén)傳送，那么可以定義dp[i][0]表示到達(dá)第i個(gè)結(jié)點(diǎn)需要的最短時(shí)間，dp[i][1]表示到達(dá)第i個(gè)傳送門(mén)的最短時(shí)間。

? 然后就定義初始值，最后寫(xiě)出轉(zhuǎn)移方程就行了

public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);// 在此輸入您的代碼...int n = scan.nextInt();//定義存儲(chǔ)竹竿x軸坐標(biāo)的數(shù)組int [] x = new int[n+1];//定義記錄每個(gè)竹竿傳送門(mén)的縱坐標(biāo)的數(shù)組int [] a = new int[n+1];//定義記錄被傳送到下一個(gè)竹竿的縱坐標(biāo)的數(shù)組int [] b = new int[n+1];//輸入竹竿縱坐標(biāo)for (int i = 1; i <= n; i++) {x[i] = scan.nextInt();}//輸入傳送門(mén)的位置和被傳送到的位置for (int i = 1; i < n; i++){a[i] = scan.nextInt();b[i+1] = scan.nextInt();}double [][] dp = new double[n+1][2];//dp[i][0]表示到達(dá)竹竿底部的最短時(shí)間//dp[i][1]表示到達(dá)竹竿傳送門(mén)的最短時(shí)間dp[1][0] = x[1];dp[1][1] = x[1]+a[1]/0.7;for (int i = 2; i <= n; i++) {dp[i][0] = Math.min(dp[i-1][0]+x[i]-x[i-1],dp[i-1][1]+b[i]/1.3);if(a[i]>b[i]) {dp[i][1] = Math.min(dp[i - 1][0] + a[i] / 0.7+x[i]-x[i-1], dp[i - 1][1]+(a[i]-b[i])/0.7);}else{dp[i][1] = Math.min(dp[i - 1][0] + a[i] / 0.7+x[i]-x[i-1], dp[i - 1][1]+(b[i]-a[i])/1.3);}}System.out.printf("%.2f",dp[n][0]);}
}

后記

? 這幾天動(dòng)態(tài)規(guī)劃的題做的比較多，其中有一些也涉及到貪心算法，也了解了一下，下一步我覺(jué)得應(yīng)該就開(kāi)始學(xué)背包問(wèn)題了，動(dòng)態(tài)規(guī)劃涉及到了0-1背包問(wèn)題，感覺(jué)是個(gè)很經(jīng)典的問(wèn)題，背包問(wèn)題又有很多分支，0-1背包問(wèn)題只是其中一個(gè)小問(wèn)題，還有很多問(wèn)題等著我去學(xué)習(xí)，看了一下去年藍(lán)橋杯的題目，感覺(jué)自己還差的有些遠(yuǎn)，算法掌握的還不夠多，接下來(lái)就要更加努力去學(xué)習(xí)了，這一個(gè)月就專心準(zhǔn)備算法，其他的事情都先放放，等到藍(lán)橋杯結(jié)束再說(shuō)。