【算法】動態規劃問題集錦與講解
來自： https://segmentfault.com/a/1190000004498566
動態規劃
維基百科對動態規劃的定義
動態規劃（英語：Dynamic programming，簡稱DP）是一種在數學、計算機科學和經濟學中使用的，通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。動態規劃常常適用于有重疊子問題[1]和最優子結構性質的問題，動態規劃方法所耗時間往往遠少于樸素解法。動態規劃背后的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再合并子問題的解以得出原問題的解。
通常許多子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，從而減少計算量：一旦某個給定子問題的解已經算出，則將其記憶化（en:memoization）存儲，以便下次需要同一個子問題解之時直接查表。這種做法在重復子問題的數目關于輸入的規模呈指數增長時特別有用.
簡言之動態規劃的思路是通過尋找最優子結構同時記錄最優結構，從而將復雜的大問題轉化為小問題的求解過程，最近針對于動態規劃做了些練習，找到些解題的思路和感覺，下面針對于幾個問題來逐步的分析下動態規劃。
動態規劃問題實例
解決動態規劃類問題，分為兩步：1.確定狀態，2.根據狀態列狀態轉移方程確定該狀態上可以執行的操作，然后是該狀態和前一個狀態或者前多個狀態有什么關聯，通常該狀態下可執行的操作必定是關聯到我們之前的幾個狀態。
數字三角形
問題描述給定一個數字三角形，找到從頂部到底部的最小路徑和。每一步可以移動到下面一行的相鄰數字上。
[2],
[3,4],
[6,5,7],
[4,1,8,3]
從頂到底部的最小路徑和為11 ( 2 + 3 + 5 + 1 = 11)。
如果采用樸素算法，我們需要記錄每次的行走軌跡，然后對其大小進行比較，最終得出結果，行走軌跡的統計是呈現指數遞增的，所以我們要采用動態規劃的方法來解決。根據我們的解決方法，先確定狀態，也就是每次向下走的一步即為一個狀態，然后是狀態轉移方程，從上一個狀態到下一個狀態，如果確定最優，當前狀態的結果，取決于上一個狀態，找到上一個狀態，然后確定上一個狀態到當前狀態轉移的方程。記錄下每一個狀態，我們通過一個二維數組來實現。
public int minimumTotal(int[][] triangle) {
// write your code here
if(triangle==null||triangle.length==0)
return 0;
int len = triangle.length;
//用來記錄每一步的狀態
int [][] cost = new int[len][len];
cost[0][0]=triangle[0][0];
for(int i=1; i<len; i++){
for(int j=0; j<triangle[i].length; j++){
//計算上一個狀態的時候，防止出現越界問題
int lower = max(0,j-1);
int upper = min(j,triangle[i-1].length-1);
//狀態轉移方程
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;
} 背包問題兩講
這里解決了兩張背包問題，一個是確定最多可以裝的下多少的背包盛放物品問題，還有一個是背包中放置的物品具有價值，要來確定其價值為多少。解決方法都是通過動態規劃來解決。
背包問題1
問題描述
在n個物品中挑選若干物品裝入背包，最多能裝多滿？假設背包的大小為m，每個物品的大小為A[i]
首先尋找狀態，確定將什么作為狀態，記錄狀態，有背包和物品，物品有放和不放兩種狀態，放置的時候可能會對應各種容量，當前的容量下可以放置進的最多的物品取決于上一個物品放置時在該狀態下所能夠達到的最大狀態和當前物品的的大小，這樣我們在最后，就可以得到每種容量下，所能放置的物品的最大數量。
public int backPack(int m, int[] A) {
// write your code here
if (A == null || 0 == A.length || m == 0)
return 0;
int len = A.length;
//初始化了一個數組，
int[][] sum = new int[len][m+1];
for(int i=0;i<len;i++){
sum[i][0] = 0;
}
for(int j=0;j<m+1;j++){
if(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個物品的體積A[i]和其價值V[i]，將他們裝入一個大小為m的背包，最多能裝入的總價值有多大？
考慮到價值問題，狀態不發生變化，只是對于狀態我們所記錄的內容方式變化，我們現在記錄的是其價值，而不是其放置的物品的大小。
public int backPackII(int m, int[] A, int V[]) {
// write your code here
if(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];
} 公共子序列，公共子串問題
公共子串
給出兩個字符串，找到最長公共子串，并返回其長度
狀態，字符串的每一位對應另一個字符串的每一個位置，因此通過一個二維數組來表示這每一個狀態位，然后是找狀態轉移方程，轉移方程即為其前一個位置的前一個的比對的結果累計當前的結果，如果相同則加1，否則為0
public int longestCommonSubstring(String A, String B) {
// write your code here
if(A==null||B==null||A.length()==0||B.length()==0)
return 0;
int lenOfA = A.length();
int lenOfB = B.length();
//狀態記錄結構
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++){
//狀態轉移
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;
} 公共子序列
給出兩個字符串，找到最長公共子序列(LCS)，返回LCS的長度。
子序列和子串的區別在于，其值不是僅僅取決于其上一個位置的對應于比對的位置的狀態，而是要尋找最大的前面的狀態值中最大的一個。
public int longestCommonSubsequence(String A, String B) {
// write your code here
if(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;
} 打劫房屋
問題描述
假設你是一個專業的竊賊，準備沿著一條街打劫房屋。每個房子都存放著特定金額的錢。你面臨的唯一約束條件是：相鄰的房子裝著相互聯系的防盜系統，且 當相鄰的兩個房子同一天被打劫時，該系統會自動報警。
給定一個非負整數列表，表示每個房子中存放的錢， 算一算，如果今晚去打劫，你最多可以得到多少錢 在不觸動報警裝置的情況下。
我們可以在通過一個數組來記錄下來，我們在每個位置打劫，所能得到的錢，在求下一個狀態的時候，遍歷前面的與其相隔的所有狀態，然后找到一個最大的，但是復雜度比較到達到了n2，空間復雜度為n，對于狀態，我們需要記錄的只有其前一個，還有與其相隔的所有狀態的最大值，因此通過兩個數字來表示即可。具體轉化方式見代碼實現。
public long houseRobber(int[] A) {
// write your code here
if(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;
//在計算最大值的時候的一個轉化
if(max2<max1)
max2 = max1;
}
return Max(max1,max2);
}
public long Max(long a,long b){
return a>b?a:b;
} 編輯距離
題目描述給出兩個單詞word1和word2，計算出將word1 轉換為word2的最少操作次數。
你總共三種操作方法：
-
插入一個字符
-
刪除一個字符
-
替換一個字符
三種操作，因此我們在一個狀態上面可以進行三種狀態的變化，確定每一個狀態，通過第二個字符串和第一個字符串的每一個位置的對應作為一個狀態，處在該狀態上，我們可以進行的操作，改，進行改操作，那么與之關聯的前一個狀態是其前一個字符對應另一個字符串的當前對應的前一個字符，增，則是說當前字符串的當前位對應到前一個字符串的前一個位置，刪，則為當前字符串的當前位對應前一個字符串的前一個位置。為了增加一個增的位置，需要我們在其前面，所以我們在兩個字符串的開始處設置一增加的位置。
public class Solution {
/**
* @param word1 & word2: Two string.
* @return: The minimum number of steps.
*/
public int minDistance(String word1, String word2) {
// write your code here
if(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)){
//狀態轉化，分別別是刪，增，改
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;
}
} 對于動態規劃的更多問題，將會繼續更新，陸續也會寫一些貪心算法等常見的算法類型。