動態(tài)規(guī)劃（英語：Dynamic programming喉恋，簡稱 DP）
是一種在數(shù)學沃饶、管理科學、計算機科學轻黑、經(jīng)濟學和生物信息學中使用的糊肤，通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。
動態(tài)規(guī)劃背后的基本思想非常簡單氓鄙。大致上馆揉，若要解一個給定問題，我們需要解其不同部分（即子問題）抖拦，再根據(jù)子問題的解以得出原問題的解升酣。
動態(tài)規(guī)劃往往用于優(yōu)化遞歸問題惩琉，例如斐波那契數(shù)列雨效，如果運用遞歸的方式來求解會重復計算很多相同的子問題，利用動態(tài)規(guī)劃的思想可以減少計算量续徽。斐波那契數(shù)列 0,1,1,2,3,5,8,13,…有著一個相當簡單的描述方式复颈，它的每個數(shù)字都與前兩個緊鄰的數(shù)字相關绩聘。如果 F(n) 是第 n 個數(shù)字，那么我們會有 F(n) = F(n-1) + F(n-2)券膀。這個在數(shù)學上稱作遞歸方程或者遞推關系君纫。為了計算后面的項，它需要前面項的計算結果作為輸入芹彬。
解決方案
自上而下：
你從最頂端開始不斷地分解問題蓄髓，直到你看到問題已經(jīng)分解到最小并已得到解決，之后只用返回保存的答案即可舒帮。這叫做記憶存儲（Memoization）会喝。
自下而上：
你可以直接開始解決較小的子問題陡叠，從而獲得最好的解決方案。在此過程中肢执，你需要保證在解決問題之前先解決子問題枉阵。這可以稱為表格填充算法（Tabulation，table-filling algorithm**）预茄。
至于迭代和遞歸與這兩種方法的關系兴溜，自下而上用到了迭代技術，而自上而下則用到了遞歸技術耻陕。
動態(tài)規(guī)劃拙徽、分治法、貪心算法異同點
相同點：
動態(tài)規(guī)劃法與分治法和貪心法類似诗宣，它們都是將問題實例歸納為更小的膘怕、相似的子問題，并通過求解子問題產(chǎn)生一個全局最優(yōu)解召庞。
不同點：
-
分治法
分治法中的各個子問題是獨立的岛心，利用子問題的解，合并成該問題的解篮灼。
-
貪心算法
只有同一個問題忘古，依賴于當前已經(jīng)做出的所有選擇。
自頂向下處理诅诱，每一步存皂，根據(jù)策略得到一個當前最優(yōu)解。傳遞到下一步逢艘，從而保證每一步都是選擇當前最優(yōu)的旦袋。
-
動態(tài)規(guī)劃
動態(tài)規(guī)劃中的各個子問題是不獨立的，動態(tài)規(guī)劃任何一個i+1階段都僅僅依賴 i 階段的處理它改，而與i之前的選擇無關疤孕。
自底向上處理，每一步央拖，根據(jù)策略得到一個更小規(guī)模的問題祭阀。最后解決最小規(guī)模的問題，得到整個問題最優(yōu)解鲜戒。
各題題解：
// ###### [爬樓梯](https://leetcode-cn.com/problems/climbing-stairs/) ★
public int climbStairs(int n) {
//思路：用動態(tài)規(guī)劃思想专控，要爬到n階，可以通過最后爬一步和兩步2中爬法到遏餐，到n階的方法等于到n-1階方法加上n-2階方法伦腐，即f(n)=f(n-1)+f(n-2)，這個f(n)方法就用遞歸實現(xiàn)
//此外失都，f(n)=f(n-1)+f(n-2)柏蘑，從n為3開始幸冻，該函數(shù)計算得出的是一個斐波那契數(shù)列，當前數(shù)為前兩個數(shù)之和咳焚，所以有兩種解法
if (n < 3) {
return n;
}
int a = 1;
int b = 2;
int cur = 0;
for (int i=3;i<=n;i++) {
cur = a + b;
a = b;
b = cur;
}
return cur;
}
// ###### [最大子數(shù)組和](https://leetcode.cn/problems/maximum-subarray/)★
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max = dp[0];
for (int i=1;i<nums.length;i++) {
//如果i前一個數(shù)的子數(shù)組和小于0洽损，就不要加上前面的累贅了，否則就加上
dp[i] = nums[i] + Math.max(dp[i-1], 0);
//遍歷的同時獲取dp數(shù)組中的最大值
if (dp[i] > max) {
max = dp[i];
}
}
return max;
}
// ###### [零錢兌換](https://leetcode.cn/problems/coin-change/)
/**
* 示例： 1 2 3 面值革半， 要湊齊5元
* 湊錢數(shù)的最小硬幣數(shù) = Min(1個1元硬幣 + 湊齊4元所需硬幣數(shù), 1個2元硬幣 + 湊齊3元所需硬幣數(shù), 1個3元硬幣 + 湊齊2元所需硬幣數(shù))
* 思路：dp[i]表示對應價格i所需最小硬幣數(shù)碑定，coins表示硬幣面值
* 則 dp[i] = min(1+dp[p-coins[j]])
*/
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
// ###### [打家劫舍](https://leetcode.cn/problems/house-robber/)
/**
* 要解前n間房能偷的最大金額，那就嘗試先從前1又官、2不傅、3間能偷的最大金額找規(guī)律
Sn表示前n間房能偷的最大金額 Hn表示第n間房的金額
示例： [1,2,3,1]
前1間房能偷的最大金額 S1 = H1 = 1
前2間房能偷的最大金額 S2 = max(S1,H1) = 2
從第三間房開始，就有2種偷法了赏胚，就是偷第n間房和不偷第n間房
偷第n間房，那就不能偷n-1間房商虐，能偷n-2間房 那么最大金額不一樣的取決于最近這三間房怎么偷觉阅，因為前Sn-2都一樣
前3間房能偷的最大金額 S3 = max(S2, H3+S1) = 4
前n間房能偷的最大金額 Sn = max(Sn-1, Hn+Sn-2)
*/
public int rob(int[] nums) {
int length = nums.length;
if(length <= 1) {
return nums[0];
}
int[] dp = new int[length]; //dp[i]表示前i間房能偷的最大金額
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for(int i=2;i<length;i++) {
dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
}
return dp[length-1]; //這里需要得到前n間房的最大值，所以是返回dp[length-1]
}
