from:https://segmentfault.com/a/1190000004498566#articleHeader4

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

代碼實(shí)現(xiàn)在https://github.com/Jensenczx/CodeEveryday
維基百科對(duì)動(dòng)態(tài)規(guī)劃的定義

動(dòng)態(tài)規(guī)劃（英語：Dynamic programming，簡(jiǎn)稱DP）是一種在數(shù)學(xué)、計(jì)算機(jī)科學(xué)和經(jīng)濟(jì)學(xué)中使用的，通過把原問題分解為相對(duì)簡(jiǎn)單的子問題的方式求解復(fù)雜問題的方法。動(dòng)態(tài)規(guī)劃常常適用于有重疊子問題[1]和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題，動(dòng)態(tài)規(guī)劃方法所耗時(shí)間往往遠(yuǎn)少于樸素解法。動(dòng)態(tài)規(guī)劃背后的基本思想非常簡(jiǎn)單。大致上，若要解一個(gè)給定問題，我們需要解其不同部分（即子問題），再合并子問題的解以得出原問題的解。

通常許多子問題非常相似，為此動(dòng)態(tài)規(guī)劃法試圖僅僅解決每個(gè)子問題一次，從而減少計(jì)算量：一旦某個(gè)給定子問題的解已經(jīng)算出，則將其記憶化（en:memoization）存儲(chǔ)，以便下次需要同一個(gè)子問題解之時(shí)直接查表。這種做法在重復(fù)子問題的數(shù)目關(guān)于輸入的規(guī)模呈指數(shù)增長(zhǎng)時(shí)特別有用.

簡(jiǎn)言之動(dòng)態(tài)規(guī)劃的思路是通過尋找最優(yōu)子結(jié)構(gòu)同時(shí)記錄最優(yōu)結(jié)構(gòu)，從而將復(fù)雜的大問題轉(zhuǎn)化為小問題的求解過程，最近針對(duì)于動(dòng)態(tài)規(guī)劃做了些練習(xí)，找到些解題的思路和感覺，下面針對(duì)于幾個(gè)問題來逐步的分析下動(dòng)態(tài)規(guī)劃。

動(dòng)態(tài)規(guī)劃問題實(shí)例

解決動(dòng)態(tài)規(guī)劃類問題，分為兩步：1.確定狀態(tài)，2.根據(jù)狀態(tài)列狀態(tài)轉(zhuǎn)移方程
確定該狀態(tài)上可以執(zhí)行的操作，然后是該狀態(tài)和前一個(gè)狀態(tài)或者前多個(gè)狀態(tài)有什么關(guān)聯(lián)，通常該狀態(tài)下可執(zhí)行的操作必定是關(guān)聯(lián)到我們之前的幾個(gè)狀態(tài)。

1.數(shù)字三角形（典型的二維數(shù)組問題）

問題描述
給定一個(gè)數(shù)字三角形，找到從頂部到底部的最小路徑和。每一步可以移動(dòng)到下面一行的相鄰數(shù)字上。

[2],
[3,4],
[6,5,7],
[4,1,8,3]

從頂?shù)降撞康淖钚÷窂胶蜑?1 ( 2 + 3 + 5 + 1 = 11)。

有一個(gè)像這樣的數(shù)字三角形:
　　　　　　　　　

? ? ? ? ? ? ? ? ? ? ? ? ７
　　　　　　３　８
　　　　　８　１　０
　　　　２　７　４　４
　　　４　５　２　６　５

從頂點(diǎn)開始,每個(gè)數(shù)字向下層走只能有左下和右下兩個(gè)方向,求出到達(dá)最后一行時(shí)最大的路徑之和.（原題）

狀態(tài)轉(zhuǎn)移方程：dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j];

---最小值問題轉(zhuǎn)移方程：dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+a[i][j];//注意邊界！！！

如果采用樸素算法，我們需要記錄每次的行走軌跡，然后對(duì)其大小進(jìn)行比較，最終得出結(jié)果，行走軌跡的統(tǒng)計(jì)是呈現(xiàn)指數(shù)遞增的，所以我們要采用動(dòng)態(tài)規(guī)劃的方法來解決。根據(jù)我們的解決方法，先確定狀態(tài)，也就是每次向下走的一步即為一個(gè)狀態(tài)，然后是狀態(tài)轉(zhuǎn)移方程，從上一個(gè)狀態(tài)到下一個(gè)狀態(tài)，如果確定最優(yōu)，當(dāng)前狀態(tài)的結(jié)果，取決于上一個(gè)狀態(tài)，找到上一個(gè)狀態(tài)，然后確定上一個(gè)狀態(tài)到當(dāng)前狀態(tài)轉(zhuǎn)移的方程。記錄下每一個(gè)狀態(tài)，我們通過一個(gè)二維數(shù)組來實(shí)現(xiàn)。----典型的兩層循環(huán)

public int minimumTotal(int[][] triangle) {// write your code hereif(triangle==null||triangle.length==0)return 0;int len = triangle.length;//用來記錄每一步的狀態(tài)int [][] cost = new int[len][len];//初始化cost[0][0]=triangle[0][0];//第一行為自身for(int i=1; i<len; i++){//i=1---后面需要減一for(int j=0; j<triangle[i].length; j++){//遍歷第i行//計(jì)算上一個(gè)狀態(tài)的時(shí)候，防止出現(xiàn)越界問題int lower = max(0,j-1);//防止j-1<0；int upper = min(j,triangle[i-1].length-1);//狀態(tài)轉(zhuǎn)移方程cost[i][j]= min(cost[i-1][lower],cost[i-1][upper])+triangle[i][j];}}int minCost = Integer.MAX_VALUE;for(int k=0; k<triangle[len-1].length; k++){minCost = min(minCost,cost[len-1][k]);}return minCost;}

2.背包問題兩講

這里解決了兩張背包問題，一個(gè)是確定最多可以裝的下多少的背包盛放物品問題，還有一個(gè)是背包中放置的物品具有價(jià)值，要來確定其價(jià)值為多少。解決方法都是通過動(dòng)態(tài)規(guī)劃來解決。

背包問題1
問題描述
在n個(gè)物品中挑選若干物品裝入背包，最多能裝多滿？假設(shè)背包的大小為m，每個(gè)物品的大小為A[i]：m=30,A[17,5,6,7,10]---最滿為28

首先尋找狀態(tài)，確定將什么作為狀態(tài)，記錄狀態(tài)，有背包和物品，物品有放和不放兩種狀態(tài)，放置的時(shí)候可能會(huì)對(duì)應(yīng)各種容量，當(dāng)前的容量下可以放置進(jìn)的最多的物品取決于上一個(gè)物品放置時(shí)在該狀態(tài)下所能夠達(dá)到的最大狀態(tài)和當(dāng)前物品的的大小，這樣我們?cè)谧詈?#xff0c;就可以得到每種容量下，所能放置的物品的最大數(shù)量。

public int backPack(int m, int[] A) {//m--背包大小---A---每個(gè)物品// write your code hereif (A == null || 0 == A.length || m == 0)return 0;//邊界條件int len = A.length;//物品個(gè)數(shù)5//初始化了一個(gè)數(shù)組，int[][] sum = new int[len][m+1];//容量for(int i=0;i<len;i++){//邊界為0初始化為0sum[i][0] = 0;//第i個(gè)商品初重}for(int j=0;j<m+1;j++){//A[0]=17,J,0-30if(j>=A[0]){sum[0][j] = A[0];}} for(int i=1;i<len;i++){for(int j=1;j<m+1;j++){if(j>=A[i]){sum[i][j] = max(sum[i-1][j], sum[i-1][j-A[i]]+A[i]);}else{sum[i][j] = sum[i-1][j];}}}return sum[len-1][m];}

背包問題2
問題描述
給出n個(gè)物品的體積A[i]和其價(jià)值V[i]，將他們裝入一個(gè)大小為m的背包，最多能裝入的總價(jià)值有多大？

考慮到價(jià)值問題，狀態(tài)不發(fā)生變化，只是對(duì)于狀態(tài)我們所記錄的內(nèi)容方式變化，我們現(xiàn)在記錄的是其價(jià)值，而不是其放置的物品的大小。

public int backPackII(int m, int[] A, int V[]) {// write your code hereif(m==0||A==null||V==null||0==A.length)return 0;int len = A.length;int [][]val = new int[len][m+1];for(int i=0;i<len; i++){val[i][0]=0;}for(int i=0; i<m+1; i++){if(i>=A[0])val[0][i]=V[0];}for(int i=1; i<len; i++){for(int j=1;j<m+1; j++){if(j>=A[i]){val[i][j] = max(val[i-1][j],val[i-1][j-A[i]]+V[i]);}else{val[i][j]=val[i-1][j];}}}return val[len-1][m];}

3.公共子序列，公共子串問題

公共子串
給出兩個(gè)字符串，找到最長(zhǎng)公共子串，并返回其長(zhǎng)度

狀態(tài)，字符串的每一位對(duì)應(yīng)另一個(gè)字符串的每一個(gè)位置，因此通過一個(gè)二維數(shù)組來表示這每一個(gè)狀態(tài)位，然后是找狀態(tài)轉(zhuǎn)移方程，轉(zhuǎn)移方程即為其前一個(gè)位置的前一個(gè)的比對(duì)的結(jié)果累計(jì)當(dāng)前的結(jié)果，如果相同則加1，否則為0

public int longestCommonSubstring(String A, String B) {// write your code hereif(A==null||B==null||A.length()==0||B.length()==0)return 0;int lenOfA = A.length();int lenOfB = B.length();//狀態(tài)記錄結(jié)構(gòu)int[][] longSubString = new int[lenOfB][lenOfA];int max = 0;for(int i=0; i<lenOfA; i++){if(B.charAt(0)==A.charAt(i)){longSubString[0][i] = 1;max = 1;}}for(int i=1; i<lenOfB; i++){for(int j=0; j<lenOfA; j++){//狀態(tài)轉(zhuǎn)移if(B.charAt(i)==A.charAt(j)){if(j-1>=0)longSubString[i][j] = longSubString[i-1][j-1]+1;else longSubString[i][j]=1;max = Max(longSubString[i][j],max);}}}return max;}

公共子序列
給出兩個(gè)字符串，找到最長(zhǎng)公共子序列(LCS)，返回LCS的長(zhǎng)度。

子序列和子串的區(qū)別在于，其值不是僅僅取決于其上一個(gè)位置的對(duì)應(yīng)于比對(duì)的位置的狀態(tài)，而是要尋找最大的前面的狀態(tài)值中最大的一個(gè)。

public int longestCommonSubsequence(String A, String B) {// write your code hereif(A==null||B==null||A.length()==0||B.length()==0)return 0;int lenOfA = A.length();int lenOfB = B.length();int [][] subsLen = new int[lenOfB][lenOfA];int max=0;for(int i=0; i<lenOfA; i++){if(A.charAt(i)==B.charAt(0)){subsLen[0][i]=1;max = 1;}} for(int i=1; i<lenOfB; i++){for(int j=0; j<lenOfA; j++){if(A.charAt(j)==B.charAt(i)){subsLen[i][j]=Max(subsLen,i-1,j-1)+1;if(subsLen[i][j]>max)max = subsLen[i][j];}}}return max;}public int Max(int[][] array,int end1,int end2){if(end2<0)return 0;int max = array[0][0];for(int i=0; i<=end1; i++){for(int j=0; j<=end2; j++){if(array[i][j]>max)max = array[i][j];}}return max;}

4.打劫房屋

問題描述
假設(shè)你是一個(gè)專業(yè)的竊賊，準(zhǔn)備沿著一條街打劫房屋。每個(gè)房子都存放著特定金額的錢。你面臨的唯一約束條件是：相鄰的房子裝著相互聯(lián)系的防盜系統(tǒng)，且當(dāng)相鄰的兩個(gè)房子同一天被打劫時(shí)，該系統(tǒng)會(huì)自動(dòng)報(bào)警。
給定一個(gè)非負(fù)整數(shù)列表，表示每個(gè)房子中存放的錢， 算一算，如果今晚去打劫，你最多可以得到多少錢 在不觸動(dòng)報(bào)警裝置的情況下。

我們可以在通過一個(gè)數(shù)組來記錄下來，我們?cè)诿總€(gè)位置打劫，所能得到的錢，在求下一個(gè)狀態(tài)的時(shí)候，遍歷前面的與其相隔的所有狀態(tài)，然后找到一個(gè)最大的，但是復(fù)雜度比較到達(dá)到了n2，空間復(fù)雜度為n，對(duì)于狀態(tài)，我們需要記錄的只有其前一個(gè)，還有與其相隔的所有狀態(tài)的最大值，因此通過兩個(gè)數(shù)字來表示即可。具體轉(zhuǎn)化方式見代碼實(shí)現(xiàn)。

public long houseRobber(int[] A) {// write your code hereif(A==null||A.length==0)return 0;int len = A.length;if(len==1)return A[0];long max1 = A[0];long max2 = A[1];for(int i=2; i<len; i++){long tmp = max2;max2 = max1+A[i];max1 = tmp;//在計(jì)算最大值的時(shí)候的一個(gè)轉(zhuǎn)化if(max2<max1)max2 = max1;}return Max(max1,max2);}public long Max(long a,long b){return a>b?a:b;}

5.編輯距離

題目描述
給出兩個(gè)單詞word1和word2，計(jì)算出將word1 轉(zhuǎn)換為word2的最少操作次數(shù)。

你總共三種操作方法：

• 插入一個(gè)字符

• 刪除一個(gè)字符

• 替換一個(gè)字符

三種操作，因此我們在一個(gè)狀態(tài)上面可以進(jìn)行三種狀態(tài)的變化，確定每一個(gè)狀態(tài)，通過第二個(gè)字符串和第一個(gè)字符串的每一個(gè)位置的對(duì)應(yīng)作為一個(gè)狀態(tài)，處在該狀態(tài)上，我們可以進(jìn)行的操作，改，進(jìn)行改操作，那么與之關(guān)聯(lián)的前一個(gè)狀態(tài)是其前一個(gè)字符對(duì)應(yīng)另一個(gè)字符串的當(dāng)前對(duì)應(yīng)的前一個(gè)字符，增，則是說當(dāng)前字符串的當(dāng)前位對(duì)應(yīng)到前一個(gè)字符串的前一個(gè)位置，刪，則為當(dāng)前字符串的當(dāng)前位對(duì)應(yīng)前一個(gè)字符串的前一個(gè)位置。為了增加一個(gè)增的位置，需要我們?cè)谄淝懊?#xff0c;所以我們?cè)趦蓚€(gè)字符串的開始處設(shè)置一增加的位置。

public class Solution {/*** @param word1 & word2: Two string.* @return: The minimum number of steps.*/public int minDistance(String word1, String word2) {// write your code hereif(word1==null||word2==null)return 0;int len1 = word1.length();int len2 = word2.length();if(len1==0||len2==0)return Max(len2,len1);int [][]dp = new int[len2+1][len1+1];for(int i=0; i<=len1; i++){dp[0][i]=i;}for(int i=0; i<=len2; i++){dp[i][0]=i;}for(int i=1; i<=len2; i++){for(int j=1; j<=len1; j++){if(word2.charAt(i-1)==word1.charAt(j-1)){//狀態(tài)轉(zhuǎn)化，分別別是刪，增，改dp[i][j] = Min(Min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]);}else{dp[i][j] = Min(Min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);}}}return dp[len2][len1];}public int Max(int a,int b){return a>b?a:b; }public int Min(int a,int b){return a<b?a:b; } }

5.N皇后問題

n皇后問題是將n個(gè)皇后放置在n*n的棋盤上，皇后彼此之間不能相互攻擊。
給定一個(gè)整數(shù)n，返回所有不同的n皇后問題的解決方案。

對(duì)于n皇后的問題，下一個(gè)皇后的布局位置將與之前的所有王后布局有關(guān)，因此通過動(dòng)態(tài)規(guī)劃，沒安置一個(gè)皇后就作為一個(gè)狀態(tài)，然后判斷之前的已經(jīng)安放的所有皇后的狀態(tài)，確定是否可以按這一個(gè)皇后，通過遞歸的方式實(shí)現(xiàn)。

public int num1(int n){if(n<1)return 0;int[] record = new int[n];return process(0,record,n); }public int process(int i,int []record,int n){if(i==n)return 1;int res = 0;for(int j=0; j<n; j++){if(isValid(record,i,j)){record[i]=j;res+=process(i+1,record,n);}}return res; }public boolean isValid(int[]record,int i,int j){for(int k=0; k<i; k++){if(j==record[k]||Math.abs(record[k]-j)==Math.abs(i-k)){return false;}}return true; }

后記

對(duì)于動(dòng)態(tài)規(guī)劃的更多問題，將會(huì)繼續(xù)更新，陸續(xù)也會(huì)寫一些貪心算法等常見的算法類型。

總結(jié)

以上是生活随笔為你收集整理的动态规划经典问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。