簡介
動態(tài)規(guī)劃是運籌學(xué)的一個分支未舟。（管理學(xué)的重要專業(yè)基礎(chǔ)課，利用統(tǒng)計學(xué)掂为、數(shù)學(xué)模型裕膀、算法等尋找復(fù)雜問題的最佳或近似最佳的答案）
動態(tài)規(guī)劃的核心是以局部最優(yōu)解求全局最優(yōu)解
重點
- 子問題
原問題由多個子問題組成
例如1+2+4+8，原問題是求四個數(shù)的和勇哗，子問題是當(dāng)前數(shù)+之前數(shù)的和 - 動態(tài)規(guī)劃狀態(tài)
即子問題可能的結(jié)果昼扛，最優(yōu)解 - 邊界狀態(tài)值
無法用子問題概括的值，例如1+2+4+8中第一個和第二個值欲诺，需要先1+2之后的值才能用當(dāng)前數(shù)+之前數(shù)的和來概括 - 狀態(tài)轉(zhuǎn)移方程
上一個子問題解如何轉(zhuǎn)換成另一個子問題的解
一抄谐、最大子序和
題目
給定一個整數(shù)數(shù)組nums，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組至少包含一個元素）扰法，返回其最大和蛹含。-
分析
- 子問題，以
i個位置上的數(shù)結(jié)尾的子數(shù)組最大和迹恐，求出每個位置的最大和挣惰，最大子數(shù)組就是其中最大的值。 - 動態(tài)規(guī)劃狀態(tài)
i個位置結(jié)尾的子數(shù)組最大和 - 邊界狀態(tài)
1位置結(jié)尾的數(shù)組最大和 - 狀態(tài)轉(zhuǎn)移方程
對于每一個位置結(jié)尾的子數(shù)組殴边，其最大值只有兩種可能
第一種憎茂，上一個位置結(jié)尾的連續(xù)數(shù)組最大值+當(dāng)前位置值（連續(xù)之前的數(shù)組）
第二種，當(dāng)前位置的值（從新開始子數(shù)組）
求這兩種操作的最大值就是當(dāng)前位置結(jié)尾的連貫子數(shù)組最大值
dp[i] = max(dp[i - 1] + num[i], mun[i])
- 子問題，以
解
class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
}
int max = dp[0];
for (int i : dp) {
max = Math.max(i, max);
}
return max;
}
}
二锤岸、爬樓梯
題目
假設(shè)你在爬樓梯竖幔，需要n(整數(shù))階才能到達樓頂。
每次可以爬1或者2個臺階是偷。
問：
有多少種方法爬到樓頂-
分析
- 子問題：原問題是到達
n階有多少種走法拳氢，n階的走法由n-1階臺階走法數(shù)量和n-2階臺階走法數(shù)量組成。因為一次只能走1或者2個臺階蛋铆，所以第n個臺階只能是由n-1或者n-2臺階走上來的馋评，且n-1和n-2走上來都只有一種方法。所以子問題就是登上n-1個臺階走法數(shù)量刺啦。 - 動態(tài)規(guī)劃狀態(tài)留特，第
i個狀態(tài)就是i個階梯的走法數(shù)量 - 邊界值狀態(tài)，第
1和第2階臺階的走法 - 狀態(tài)轉(zhuǎn)移方程，
dp[i] = dp[i-1] + dp[i-2]
- 子問題：原問題是到達
解
- 設(shè)置遞推數(shù)組 dp[n]蜕青，dp[i]代表到達第
i階時有多少種走法 - 設(shè)置
dp[1]和dp[2]的值苟蹈，即第一階和第二階的走法數(shù)量 - 利用
i循環(huán)遞推，從3到n階計算結(jié)果
class Solution {
public int climbStairs(int n) {
if(n == 1) {
return 1;
}
if(n == 2) {
return 2;
}
int[] dp = new int[n];
dp[0] = 1;
dp[1] = 2;
for(int i=2; i<n ;i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n - 1];
}
}
三右核、打家劫舍
問題
你是一個專業(yè)的小偷慧脱，計劃沿街竊取錢財。街上排列有若干房屋贺喝，相鄰房屋裝有相同的防盜系統(tǒng)菱鸥，如果兩個房屋都失竊會自動報警。
問：
給定一個代表存放金額的非負數(shù)數(shù)組搜变，計算不觸發(fā)報警情況下能達到最高金額-
分析
- 子問題采缚，原問題是盜竊到最后一家或倒數(shù)第二家時能夠獲得的最大財寶數(shù)量针炉。子問題就是求每個房間的最優(yōu)解
- 動態(tài)規(guī)劃狀態(tài)挠他，
i個房間的狀態(tài)就是該房間能獲得財寶的最大值 - 邊界， 第一個房間篡帕，第二個房間能獲得的最大財寶
- 轉(zhuǎn)移方程殖侵，
i個房間最大值有兩種可能，一種是選擇當(dāng)前房間镰烧，另一種是不選擇當(dāng)前房間
選擇：不能盜竊相鄰房間拢军，所以值為i-2間房最大值+當(dāng)前房間財寶值
不選擇：上一間的最大值
再挑選選擇和不選擇中的最大值就是當(dāng)前房間的最大值
dp[i] = max(dp[i-2] + num[i], dp[i-1])
解
class Solution {
public int rob(int[] nums) {
// 邊界情況
if (nums.length == 0) {
return 0;
} else if (nums.length == 1) {
return nums[0];
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[nums.length - 1];
}
}
四、零錢兌換
題目
給定不同面額的硬幣 coins 和一個總金額 amount怔鳖。編寫一個函數(shù)來計算可以湊成總金額所需的最少的硬幣個數(shù)茉唉。如果沒有任何一種硬幣組合能組成總金額，返回 -1结执。
coins[1, 2, 5], amount = 11-
分析
- 子問題度陆，
1...amount最少硬幣組合數(shù)，例如amount = 11時最小組合就是amount = 10献幔、amount = 9懂傀、amount = 6時組合數(shù)+1中最小的。子問題就是總金額1到amount的最優(yōu)解 - 動態(tài)規(guī)劃狀態(tài)蜡感，
amount = i時的最小組合數(shù) - 邊界蹬蚁，當(dāng)硬幣數(shù)額等于
amount時dp[amount] = 1,即一枚硬幣就能組合成總金額 - 轉(zhuǎn)移方程，
min(dp[i] = dp[i-coin])郑兴，coins數(shù)組中元素帶入方程后的最小值
- 子問題度陆，
public static int coinChange(int[] coins, int amount) {
if (amount == 0) {
return 0;
}
int[] dp = new int[amount + 1];
int coinsMin = coins[0];
for (int i : coins) {
if (i <= amount) {
dp[i] = 1;
coinsMin = Math.min(coinsMin, i);
}
}
for (int i = coinsMin * 2; i <= amount; i++) {
for (int j : coins) {
if (i - j > 0 && i - j <= amount && dp[i - j] > 0) {
if (dp[i] == 0) {
dp[i] = dp[i - j] + 1;
} else {
dp[i] = Math.min(dp[i], dp[i - j] + 1);
}
}
}
}
return dp[amount] == 0 ? -1 : dp[amount];
}
五犀斋、地下城游戲
題目
一些惡魔抓住了公主（P）并將她關(guān)在了地下城的右下角。地下城是由 M x N 個房間組成的二維網(wǎng)格情连。我們英勇的騎士（K）最初被安置在左上角的房間里叽粹，他必須穿過地下城并通過對抗惡魔來拯救公主。
騎士的初始健康點數(shù)為一個正整數(shù)。如果他的健康點數(shù)在某一時刻降至 0 或以下球榆，他會立即死亡朽肥。
有些房間由惡魔守衛(wèi)，因此騎士在進入這些房間時會失去健康點數(shù)（若房間里的值為負整數(shù)持钉，則表示騎士將損失健康點數(shù)）衡招；其他房間要么是空的（房間里的值為 0），要么包含增加騎士健康點數(shù)的魔法球（若房間里的值為正整數(shù)每强，則表示騎士將增加健康點數(shù)）始腾。
為了盡快到達公主，騎士決定每次只向右或向下移動一步空执。分析
看到題目首先想到的是從dungeon[0][0]開始浪箭，計算向右或向下過程中扣除或增加的總血量，但是制定轉(zhuǎn)移方程的時候卻有個問題辨绊，判斷向右或是向下的時候需要考慮兩個變量奶栖，一個是總血量，另一個是最低血量门坷。需要在追求總血量最小的時候保證路徑中任意一格時血量都在0之上宣鄙。
看了官方解答，正確的解法是從dungeon[m - 1][n - 1]也就是公主所在處規(guī)劃默蚌。計算每個格子達到終點需要多少初始值冻晤，則有轉(zhuǎn)移方程dp[i][j] = min(1 - dp[i - 1][j], dp[i][j - 1])。意為從下一步需要的初始值推算當(dāng)前需要的初始值绸吸。又因為初始值必須大于1鼻弧，所以調(diào)整一下轉(zhuǎn)移方程dp[i][j] = max(1, min(1 - dp[i - 1][j], dp[i][j - 1])),使其小于1則初始值為1。解
class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int n = dungeon.length;
int m = dungeon[0].length;
int[][] dp = new int[n][m];
dp[n - 1][m - 1] = Math.max((1 - dungeon[n - 1][m - 1]), 1);
for (int i = m - 2; i >= 0; i--) {
dp[n - 1][i] = Math.max(dp[n - 1][i + 1] - dungeon[n - 1][i], 1);
}
// 只有一行的情況下锦茁，直接返回
if (dungeon.length == 1) {
return dp[0][0];
}
for (int i = n - 2; i >= 0; i--) {
dp[i][m - 1] = Math.max(dp[i + 1][m - 1] - dungeon[i][m - 1], 1);
}
for (int i = n - 2; i >= 0; i--) {
for (int j = m - 2; j >= 0; j--) {
dp[i][j] = Math.max(1, Math.min(dp[i + 1][j] - dungeon[i][j], dp[i][j + 1] - dungeon[i][j]));
}
}
return dp[0][0];
}
}
