什麼是動态規劃
動态規劃的主要思想是把問題劃分為一個個子狀态，一個狀态的最優解往往是基于其前一個狀态的最優解。兩個狀态之間的關系，我們就稱之為狀态轉移方程。這裡引出了狀态和狀态轉移方程的概念：狀态是一個目前的值，這個值是通過前一個值以及狀态轉移方程推得的。在解決動态規劃問題的時候，我們往往會把問題模組化為一個一維數組或是二維數組，處理完邊界值之後，就可以通過前一個狀态和後一個狀态的遞推關系循環解出軸上的一個個狀态值。如果說貪心算法是為了達到目的追求局部最優，簡單粗暴，那麼動态規劃就是一種相對嚴密，統籌全局的算法。
動态規劃的特點
1、空間換時間：動态規劃把最終問題的求解分解為一個個子結構，我們可以稱之為最優子結構，在求解出最終結果前，我們把之前的每一個狀态的最優解存儲在了數組中，後面的狀态的求解基于之前的結果，這樣可以節省時間，但需要一些存儲空間來放這些值，這就是空間換時間。
2、題目提供的往往是一些具有一定屬性的對象，然後用他們去達成某種總體最優的目标。
3、動态規劃問題的求解數組可以是一維的也可以是二維的。
4、重疊子結構：在求解一個大問題的過程中需要多次求解某個小問題，而小問題的解我們已經得到，直接取出來使用即可。
5、無後效性：某個狀态的求解隻與它之前的狀态有關，而與它後面的狀态沒有關系。
動态規劃解題步驟
1、确定狀态：首先找到題目中變化的量，和求解目标對應的變量，一般我們可以基于這些量建構一個一維或者二維數組。
2、确定遞推方向：分析題目要求，确定求解數組狀态的循環初始位置和遞推方向。
3、處理數組邊緣值：定義數組後，往往我們會把邊緣值置0。若目标值為0，對應的狀态的解自然也是0，邊界的0的部分需要我們主動加上去，大家也要格外注意一下dp下标和數組下标因為引入0導緻的偏移。
4、在循環中求解數組：即通過循環，去遞推一個個子狀态的值。這個時候需要注意狀态轉移方程，狀态之間的關系變化。
5、選出需要的最優解。
動态規劃題型1：錢币選擇問題
問題描述：給你若幹面值為1,3,5，數量不限的錢币，給一個目标值，需要用最少的錢币數量湊齊目标值。
解題思路：使用動态規劃，先确定湊0元需要0個錢币，湊1元至少需要一個1元錢币；湊2元至少兩個1元錢币；湊3元時選擇一個3元硬币比選擇3個1元硬币更優，故選擇一個3元硬币；湊四元的時候我們選擇用到前面的結果，隻要再加上一進制硬币即可，當然在選擇這個方案前我們比對過（4-1）元、（4-3）元、（4-5）元的幾種情況。由于之前的計算結果都已經最優，是以我們隻要考慮最後一張錢币拿的是一進制、三元、還是五元即可。這樣一來，我們可以遞推得到任意狀态的解。
算法實作：
/**
* 動态規劃1：錢币選擇問題
*/
public void dp1()
{
int[] money={1,3,5,7};
int sum=24;
int result = DP1(money,sum);
System.out.println(result);
}
/**
* 動态規劃1：錢币選擇問題
* @return
*/
private int DP1(int[] money,int sum)
{
int[] number = new int[sum+1];
for(int m =0;m<number.length;m++)//初始化一個較大的值
{
number[m]=m;
}
for(int i=1;i<=sum;i++) //循環擷取不同面值對應的最小數量
{
for(int j=0;j<money.length;j++) //循環拿可能情況進行比對
{
if(i>=money[j]&&number[i-money[j]]+1<number[i]) //滿足更小條件則指派
number[i]=number[i-money[j]]+1; //如果發現有更小的情況就更新數值
}
}
return number[sum];
}
動态規劃題型2：求三角形路徑數字最大和(自頂至底)
題目描述：給你一個類似二叉樹的結構，每個節點都有相應的值，現求自頂至底的路徑的最大數字和。
解題思路：其實這題自頂至底或者自低至頂都是可以的，我們這裡選擇前者來求解。我們隻要把資料存入一個二維數組，然後從頂端往下依次推得到達每個節點的最大數字和。
算法實作：
/**
* 動态規劃2：求三角形路徑數字最大和(自頂至底)
*/
public void dp2()
{
int[][] a = new int[5][5];
Scanner sc = new Scanner(System.in);
System.out.println("請輸入數組的每一個數:");
for(int i=0;i<5;i++)
{
for(int j=0;j<i+1;j++)
{
a[i][j]=sc.nextInt();
}
}
int sum = DP2(a);
System.out.println("最大和為："+sum);
}
/**
* 動态規劃2：求三角形路徑最大數字和(自頂至底)
* @param a
* @param i
* @param j
* @return
*/
private int DP2(int[][] a) {
int[][] sum = new int[a.length][a.length];
sum[0][0]=a[0][0];
int max=0;
for(int i=1;i<a.length;i++)
{
for(int j=0;j<i+1;j++)
{
if(j>0&&j<i&&sum[i-1][j-1]+a[i][j]>sum[i-1][j]+a[i][j])
sum[i][j]=sum[i-1][j-1]+a[i][j];
else if(j>0&&j<i&&sum[i-1][j-1]+a[i][j]<=sum[i-1][j]+a[i][j])
sum[i][j]=sum[i-1][j]+a[i][j];
else if(j==0)
sum[i][j]=sum[i-1][j]+a[i][j];
else if(j==i)
sum[i][j]=sum[i-1][j-1]+a[i][j];
System.out.println(i+","+j+"最大和："+sum[i][j]);
if(i==a.length-1&&max<sum[i][j])
max=sum[i][j];
}
}
return max;
}
動态規劃題型3：求最長非降子序列長度
題目描述：求某序列的最長非降子序列長度。
解題思路：設數組上每個值為一條非降子序列的末端，這條子序列的長度就是數組的狀态。每個狀态都與前一個狀态有關。
算法實作：
/**
* 動态規劃3：求最長非降子序列長度
*/
public void dp3()
{
int[] a= {5,3,4,3,9,11,7};
int length = DP3(a);
System.out.println(length);
}
/**
* 動态規劃3：求最長非降子序列長度（LCS）
* @param a
* @return
*/
public int DP3(int[] a)
{
int length=1;
int[] len = new int[a.length];
len[0]=1;
for(int i=1;i<a.length;i++)
{
if(a[i]>a[i-1])
len[i]=len[i-1]+1;
else
len[i]=1;
if(length<len[i])
length=len[i];
}
return length;
}
動态規劃題型4：求最長公共子序列
題目描述：給定兩個序列，求它們的最長公共子序列，子序列不要求連續（這裡的子序列可以了解為删除序列上任意節點後餘下的部分組成的序列）
解題思路：這題也可以用動态規劃來解，這裡涉及到兩條序列，我們使用二維數組，一個角标來表示第一個序列的某字元位置，另一個角标來表示另一個序列的某字元位置。狀态值的表示即兩個角标左側的兩個序列段的最長公共子序列長度。角标左移後得到的是目前狀态的前一個狀态，比如目前a[i]=b[j]，那麼如果令i和j都減一，那麼最長公共子序列長度減一；若a[i]！=b[j]，且數組a的角标左移後最長子序列會減小，那麼不能移動這個角标，而應該移動j，若兩段序列還有相同部分，那麼a[i]還會再次等于b[j]。是以，在這個題型裡我們依然可以找到子狀态之間的遞推關系。
算法實作：
/**
* 動态規劃3：求最長非降子序列長度
*/
public void dp3()
{
int[] a= {5,3,4,3,9,11,7};
int length = DP3(a);
System.out.println(length);
}
/**
* 動态規劃3：求最長非降子序列長度（LCS）
* @param a
* @return
*/
public int DP3(int[] a)
{
int length=1;
int[] len = new int[a.length];
len[0]=1;
for(int i=1;i<a.length;i++)
{
if(a[i]>a[i-1])
len[i]=len[i-1]+1;
else
len[i]=1;
if(length<len[i])
length=len[i];
}
return length;
}
動态規劃題型5: 01背包問題
題目描述：給定若幹物品，它們有一定的重量和價值，以及一個有一定容量上限的背包，物品每種類型隻有一個且在裝包時隻可以選擇裝或者不裝，不能裝一部分。求背包所能容納的最大價值。
解題思路：因為是物品隻能選擇裝或者不裝，那麼就不适合采用貪心算法了，此題我們用動态規劃來解。首先我們來找我們需要求解的狀态，這裡涉及到兩個變化的量，一個是選擇物品的種類，一個是背包的容量（背包的容量類似于我們之前求湊錢币的題的那個總金額）。這題和例題1的差別是這題背包可能會有一些空間剩餘，而例題一中必須要湊齊指定金額。在這題中，我們要求出在不同背包容量下的最大價值，在某一定的容量下，還需要去考慮不同物品的選擇。假定我們隻選擇物品A，然後求出在不同背包容量下的最大價值，這顯然都是相同的。這時我們再加上物品B，再去推導不同背包容量下的最大價值，這是受到物品A的影響的，我們要選擇是否放物品B。以此類推，我們可以得到在選擇任意物品和任意背包容量下的最大價值。是以這題我們選擇二維數組，表示不同種類物品數量的選擇和背包的容量。
算法實作：
/**
* 動态規劃5:01背包問題（物品有重量和價值，且隻有一個，去放置到定容的包中）
*/
public void dp5()
{
int[] w = {3,4,5}; //重量
int[] v = {4,5,6}; //價值
int m = 8; //背包最大總容量
int n = 3; //物品種類數量
int value = DP5(w,v,m,n);
System.out.println(value);
}
/**
*
* 動态規劃5:01背包問題
* @param w：物品重量
* @param v：物品價值
* @param m：背包容量
* @param n： 物品種類數量
*/
public int DP5(int[] w , int[] v , int m ,int n)
{
int max=0;
int[][] dp = new int[n+1][m+1];
for(int i = 0 ;i<n+1;i++)
dp[i][0]=0;
for(int i = 0 ;i<m+1;i++)
dp[0][i]=0;
for(int i = 1;i<n+1;i++) //以放的物品數量為尺度
{
for(int j=1;j<m+1;j++)
{
if(w[i-1]>j) //不放
dp[i][j]=dp[i-1][j]; //總價值和之前的情況相同，少了這個物品，用之前的物品去填充這個包
else //放，繼續分類
{
if(dp[i-1][j-w[i-1]]+v[i-1]>dp[i-1][j])//假設這個物品已經放了，然後推其總價值和不放這個物品的最優解比較，選大的
dp[i][j]=dp[i-1][j-w[i-1]]+v[i-1];
else
dp[i][j]=dp[i-1][j];
}
if(dp[i][j]>max) //篩選最大值
{
max=dp[i][j];
}
}
}
return max;
}
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)