動(dòng)態(tài)規(guī)劃學(xué)習(xí)總結(jié)
最近在學(xué)習(xí)算法，希望寫一篇博客來(lái)記錄自己學(xué)習(xí)過程和總結(jié)一下自己學(xué)到的東西，方便以后的歸納整理。我覺得寫博客是一種很好的整理知識(shí)點(diǎn)的方法，在寫的過程你可以認(rèn)認(rèn)真真的去歸納知識(shí)點(diǎn)薛匪，發(fā)現(xiàn)自己理解的不到位的地方，從而去提高自己脓鹃。雖然需要花點(diǎn)時(shí)間逸尖，但是很有幫助。
下面我將從三個(gè)方面來(lái)介紹動(dòng)態(tài)規(guī)劃的內(nèi)容瘸右。
1.動(dòng)態(tài)規(guī)劃介紹
2.動(dòng)態(tài)規(guī)劃的解題思路
3.動(dòng)態(tài)規(guī)劃例題分析
[TOC]
動(dòng)態(tài)規(guī)劃介紹
1.什么是動(dòng)態(tài)規(guī)劃
動(dòng)態(tài)規(guī)劃就是一種用來(lái)解決最優(yōu)化問題的算法思想娇跟。簡(jiǎn)單來(lái)說(shuō)，動(dòng)態(tài)規(guī)劃將一個(gè)復(fù)雜的問題分解成若干個(gè)子問題太颤，通過綜合子問題的最優(yōu)解來(lái)得到原問題的最優(yōu)解苞俘。需要注意的是，動(dòng)態(tài)規(guī)劃會(huì)將每個(gè)求解的子問題的解都記錄下來(lái)龄章。這樣當(dāng)下次碰到同樣的子問題的時(shí)候 吃谣，直接使用之前記錄的結(jié)果。而不是重復(fù)計(jì)算做裙。
按我的理解來(lái)說(shuō)岗憋，動(dòng)態(tài)規(guī)劃就是 自底向上求解，而一般的遞歸是自頂向下求解菇用。當(dāng)我們使用自底向上求解的時(shí)候澜驮，我們解決問題的時(shí)間復(fù)雜度就可以轉(zhuǎn)化為O(n),從而大大優(yōu)化我們的算法。但是問題來(lái)了惋鸥，我們?nèi)绾巫缘紫蛳虑蠼饽卦忧睿灰保覀兿葋?lái)了解動(dòng)態(tài)規(guī)劃的基本性質(zhì)卦绣。
2.動(dòng)態(tài)規(guī)劃三個(gè)重要概念
1.邊界
邊界問題是動(dòng)態(tài)規(guī)劃很重要的一個(gè)問題耐量，因?yàn)槲覀冊(cè)谶M(jìn)行N次循環(huán)迭代的時(shí)候，要先找出初始問題的最優(yōu)解滤港，這就是我們說(shuō)到底邊界問題廊蜒。及求出F(1),F(2)等初始值的最優(yōu)解，一般這些邊界的解我們很容易就可以得到溅漾。當(dāng)我們分析出邊界的最優(yōu)解時(shí)山叮，就可以通過循環(huán)迭代來(lái)求出整個(gè)問題的最優(yōu)解。
2.最優(yōu)子結(jié)構(gòu)
最優(yōu)子結(jié)構(gòu)就是我們分解的每個(gè)子問題的解添履。由于動(dòng)態(tài)規(guī)劃是自底向上求解屁倔，所以我們?cè)诘拈_始，只需要找到初始的計(jì)算邊界問題暮胧，求出F(1),F(2)最小子問題的最優(yōu)解锐借，然后試著去尋找規(guī)律。
3.狀態(tài)轉(zhuǎn)移方程
狀態(tài)轉(zhuǎn)移方程是動(dòng)態(tài)規(guī)劃的核心往衷，決定了問題的每一階段和下一階段的關(guān)系钞翔。我們?cè)谘h(huán)迭代的時(shí)候，其實(shí)每次迭代的核心邏輯就是使用狀態(tài)轉(zhuǎn)移方程尋找下一問題的最優(yōu)解席舍。
4.動(dòng)態(tài)規(guī)劃的適用場(chǎng)景
當(dāng)我們遇到求什么最大值布轿，最小值，最短路徑等等類似問題的時(shí)候来颤，我就就可以考慮是不是可以用動(dòng)態(tài)規(guī)劃的算法來(lái)解決問題汰扭。
說(shuō)了這么多是不是有種一臉懵逼的感覺，我是誰(shuí)脚曾？我在哪东且？我要干什么？喝口咖啡本讥，下面咋們來(lái)通過一道例題來(lái)分析動(dòng)態(tài)規(guī)劃的解題套路珊泳。
動(dòng)態(tài)規(guī)劃解題思路
在學(xué)習(xí)了幾道動(dòng)態(tài)規(guī)劃的問題后，我覺得動(dòng)態(tài)規(guī)劃問題還是有固定的解題思路的拷沸，下面我將自己的總結(jié)分享給大家色查。
首先先來(lái)一道例題。對(duì)應(yīng)為L(zhǎng)eetcode第53題撞芍。
給定一個(gè)整數(shù)數(shù)組 nums 秧了，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和序无。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大验毡，為 6衡创。
拿到這道題，一看是求最大和晶通，那就拿動(dòng)態(tài)規(guī)劃的方式來(lái)解決這道題吧璃氢。我們把動(dòng)態(tài)規(guī)劃的三大核心概念去分析這道題。
給定dp[]存儲(chǔ)每個(gè)子問題的最優(yōu)解,mums[]為給定的數(shù)組狮辽。
1.邊界問題一也。
當(dāng)給定的數(shù)組長(zhǎng)度為0是，我們返回0.
2.最優(yōu)子結(jié)構(gòu)
本題是分析n數(shù)組的最大連續(xù)子數(shù)組的和喉脖，我們可以先求數(shù)組長(zhǎng)度為1時(shí)的最優(yōu)解椰苟，及F（1）的最優(yōu)解。
F（1）：只能取-2 树叽，所以F（1）的最優(yōu)解為-2
F（2）：1> -2+1 > -2, 所以F（2）的最優(yōu)解為1
F（3）：.........
3.狀態(tài)轉(zhuǎn)移方程
F(n) = max（nums[n], nums[n] + F(n)）
為什么狀態(tài)轉(zhuǎn)移方程是這樣的呢舆蝴。我們來(lái)分析一下。
首先題目要求的是 連續(xù)子數(shù)組,我們必須保證我們所取到的每一個(gè)子問題的最優(yōu)子結(jié)構(gòu)都是連續(xù)子數(shù)組菱皆。所以我們從F（2）開始只有兩種選擇须误。
1.只選擇nums[2]
2.選擇 nums[2] + F（1）
這樣才能保證取到的數(shù)組是連續(xù)子數(shù)組，我們只需要去取這兩個(gè)結(jié)果 的最大值仇轻。
動(dòng)態(tài)規(guī)劃例題分析
最大子序和代碼分析
public int maxSubArray(int[] nums) {
int maxSum = nums[0]; //maxSum為最終結(jié)果
int curSum = 0; //curSum為動(dòng)態(tài)和數(shù)
for (int i = 0; i < nums.length; i++) {
if (curSum < 0) {
//curSum<0京痢，那么curSum沒有利用價(jià)值了，直接至0篷店；curSum>0祭椰，之后才有可能加出更大的和
curSum = 0;
}
curSum += nums[i];
if (curSum > maxSum) {
maxSum = curSum;
}
}
return maxSum;
}
理解動(dòng)態(tài)規(guī)劃我們可以先從簡(jiǎn)單問題入手，先把簡(jiǎn)答的問題搞懂然后一步一步去理解更難的動(dòng)態(tài)規(guī)劃問題疲陕。當(dāng)然自己在平時(shí)還要多看代碼方淤，理解別人的解題思路。
