一、貪心算法

參考
算法（一）：貪心

我們今天介紹的主題是貪心算法。這是相對比較容易的一種算法。我這里不敢給出嚴(yán)格定義，因?yàn)槲耶?dāng)年領(lǐng)悟貪心和動(dòng)態(tài)規(guī)劃的無后效性用了三年時(shí)間。從我第一次聽說無后效性到終有一天恍然大悟，總共用去了一千天。所以，我這里就不講定義，咱們直接看例子。

貪心算法，如果不用手動(dòng)證明一個(gè)問題的數(shù)學(xué)性質(zhì)的話，其實(shí)是比較簡單的。

1.例1

有一個(gè)背包，其最大容量是50KG，現(xiàn)在有各種不同價(jià)值的液體，比方說，有水，其價(jià)值是10 每千克，共100KG；酒精，其價(jià)值是20 每千克，共30KG；有油，價(jià)值25每千克，共30KG。問什么樣的方案才能使得背包里裝的液體的總價(jià)值最大？顯然，這是一道小學(xué)生都會(huì)的題目，揀貴的裝唄。這誰不會(huì)。那就是把30KG油先裝了，因?yàn)橛妥钯F嘛，剩下20KG的容量裝酒精，因?yàn)榫凭人F。

好，那么，這個(gè)思維過程就是貪心：每一階段做決策都找出當(dāng)前條件下的最優(yōu)解。當(dāng)然這個(gè)問題，這種解法的正確性顯而易見，貪心類的問題最難的地方在于正確性無法證明。這個(gè)我們先不管。畢竟我們不是在做算法研究，我們只要能用貪心去解決具體的編程問題就行了。

2.例2

再看一個(gè)簡單的例子。在商店找零，比如說，售貨員要找給你37塊錢，那什么樣的方案才是找錢的張數(shù)最少的方案呢？肯定是找回的零錢面值越大，最后的張數(shù)越少。所以我們可以使用貪心的方法來解決這個(gè)問題。先找一張20的，如果再找一張20的，那就超過37了，這不行，所以就再找一張10塊的，然后是5塊的和兩張一塊的。最終的方案就得到了，這也是一次典型的貪心計(jì)算方案。

3.例3

在貪心的思想的指導(dǎo)下，也設(shè)計(jì)了一種排序算法，這種算法被稱為選擇排序。排序的思想很簡單。既然我的目標(biāo)是把一堆數(shù)字從小到大排，那么我按階段解決這個(gè)問題不就好了么？第一步找到最小的那個(gè)數(shù)把它放到第一位，第二步在剩下的所有數(shù)里再找最小的，把它放到第二位，依次類推。

二、分治算法 （divide and conquer,D&C）

參考
算法設(shè)計(jì)（二）：分治
一個(gè)小姑娘在圖書館借了一大摞書，抱著出門，警報(bào)響了，小姑娘正準(zhǔn)備一本本地去試看是哪一本還沒有消磁，管理員大媽驚呼：“這得試到什么時(shí)候了." 然后大媽就把書分了兩半，去試一下沒有響，再把剩下的那一半書再分兩半。大媽的這種解法就叫分治。這也是算法設(shè)計(jì)的一個(gè)例子。小姑娘的解法的時(shí)間復(fù)雜度是O(n)，大媽解法的時(shí)間復(fù)雜度是O(log n)。當(dāng)然，段子下面早就有人回復(fù)：如果不止一本書沒有消磁，大媽解法就掛了。

分治算法，通過把問題分解為更小的子問題，先解決小問題，再把小問題的解合并起來的一種方法。通常，如果子問題的規(guī)模仍然很大，可以繼續(xù)拆解成更小的任務(wù)，更進(jìn)一步，實(shí)踐中，大任務(wù)往往與子任務(wù)有相同的結(jié)構(gòu)，以便于遞歸地進(jìn)行任務(wù)拆解。

1.例1

以具體的例子來說明?，F(xiàn)在一共9枚硬幣，已知其中有一枚是假的，它比其他8枚都要輕。現(xiàn)在有一個(gè)天平，只稱兩次，能找到這枚硬幣嗎？

我們倒著想，假如現(xiàn)在有兩枚，稱一次，這很簡單，天平高的那一邊的是假幣，如果有三枚呢？那就有兩種情況，如果天平平衡，那么未稱的那枚是假幣，如果天平不平衡，高的那邊是假幣。

再往上一層，如果有9枚硬幣，我們可以把它分為三堆，一堆3個(gè)，然后任選兩堆放在天平上稱，如果天平平衡，那么假幣一定在沒稱的那一堆里，如果天平不平衡，那么假幣就在天平高起的那一堆里。

這個(gè)例子就是一個(gè)很好的分治的例子，我們先把規(guī)模為9的大問題，分拆為規(guī)模為3的小問題，而且這個(gè)小問題與大問題保持了相同的性質(zhì)。然后再去解決規(guī)模為3的小問題，就得到最終的答案了。

2.解題步驟

分治法有三個(gè)解題步驟，無論是簡單的分治還是復(fù)雜的，都逃不開這個(gè)標(biāo)準(zhǔn)步驟。它們是：

• 拆解子任務(wù)
• 解決子任務(wù)
• 合并子任務(wù)的解

分治算法應(yīng)用在方方面面，一般來說，解決子任務(wù)這一步驟相對容易，因?yàn)楫?dāng)子任務(wù)拆到規(guī)模一定小的情況下，解就會(huì)顯得非常簡單。分治算法的應(yīng)用難點(diǎn)一般都會(huì)出現(xiàn)在拆解子任務(wù)與合并解的步驟上。

3.例2

給定一堆平面上的坐標(biāo)，找出平面上的距離最近的點(diǎn)。暴力地一對對地去查找，這個(gè)辦法的時(shí)間復(fù)雜度是O(n^2)，我們能不能使用分治來加速呢？實(shí)際上是可以的。但是這個(gè)問題的子問題分拆就沒有那么簡單了。

我們嘗試著拆分一下，把這個(gè)平面一分為二，那么距離最小的點(diǎn)可能出現(xiàn)在左邊，也可能出現(xiàn)在右邊。假如，我們已經(jīng)把左邊最近的兩個(gè)點(diǎn)找出來了，又把右邊最近的兩個(gè)點(diǎn)找出來了。那么合并這兩個(gè)子問題的時(shí)候，只需要再比較這個(gè)子問題的解，看是哪一邊的點(diǎn)更近。

但是等等，我們漏了一點(diǎn)東西。

image.png

看這幅圖，假如，左邊那個(gè)平面里，找到的最近的一對點(diǎn)是1和2，右邊找到的最近的一對是3和4。解合并的時(shí)候，如果是檢查1，2和3，4之間的距離誰更小是不行的，因?yàn)槊黠@這個(gè)平面上，距離最近的一對點(diǎn)是2和3。也就是說在進(jìn)行平面點(diǎn)的拆分的時(shí)候時(shí)候，就已經(jīng)把2和3這一對最近的點(diǎn)拆開了，那么我們在合并的時(shí)候就要考慮這個(gè)問題。這個(gè)子問題的解合并是一個(gè)非常難的事情，這節(jié)課就不展開講了。（以后還有沒有機(jī)會(huì)再講，看情況吧）

總之，使用分治算法解題的時(shí)候，如何正確地拆解問題，合并問題是設(shè)計(jì)算法的核心所在。

4.例3

所有的分治算法中，最常用的，還是二分法。二分通?？梢允沟脝栴}的規(guī)模減半。

我們最常見的一個(gè)游戲，猜數(shù)字。我選定一個(gè)數(shù)字，在0到100之間，你來猜，如果猜得比選定數(shù)字大，我會(huì)提示你猜高了，如果比選定數(shù)字小，我會(huì)提示你猜低了。那么最多需要幾次就一定能猜對呢？

我們常用的策略就是二分，先報(bào)50，如果主持人說低了，那我就知道，這個(gè)數(shù)字一定位于50，100這個(gè)區(qū)間，那我再報(bào)75。這樣每次都能把待選區(qū)減少一半。所以最多需要7次就可以找到這個(gè)數(shù)字。如果是1到1000，只需要10次(從這里也可以看到O(log n)是一種時(shí)間復(fù)雜度很好的算法了，畢竟一百萬地規(guī)模也只要20次。)

我們上面舉的例子就是二分法，在一個(gè)已經(jīng)有序的數(shù)組里進(jìn)行查找，我們通常稱之為二分查找(Binary Search)。

5.排序算法中最常用的快速排序和合并排序也是分治算法的經(jīng)典案例

三、《算法圖解》第9章 動(dòng)態(tài)規(guī)劃

image.png

1.簡單算法

最簡單的算法是嘗試各種商品組合，并找出價(jià)值最高的組合。在有3件商品的情況下，需要計(jì)算8個(gè)不同的集合。在有4件時(shí)，需要計(jì)算16個(gè)集合。算法 復(fù)雜度達(dá)到了O(2^N)

2.貪婪算法

這個(gè)例子出現(xiàn)在《算法圖解》第8章，背包只能裝35磅，商品有以下3種可以偷：

• 音響 3000美元 30磅
• 電腦 2000美元 20磅
• 吉他 1500美元 15磅

貪心算法的原則就是挑最貴的去偷，裝上30磅的音響，價(jià)值3000美元，別的東西就裝不下了。
實(shí)際上，電腦加上吉他正好35磅，總計(jì)價(jià)值是3500美元。在這里，貪心策略顯然不是最優(yōu)解，但非常接近。

有些情況下，完美是優(yōu)秀的敵人。如果只需要找到一個(gè)大致能解決問題的算法，就可以用貪心策略，它們實(shí)現(xiàn)起來非常容易，得到的結(jié)果又與正確結(jié)果相當(dāng)接近。

3.動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃先解決子問題，再逐步解決大問題。每個(gè)動(dòng)態(tài)規(guī)劃算法都從一個(gè)網(wǎng)格開始，背包問題網(wǎng)格如下：

image.png

網(wǎng)格最初是空的，動(dòng)態(tài)規(guī)劃就是逐步將網(wǎng)格填滿。

吉他行

第一個(gè)單元格表示背包的容量為1磅。 吉他的重量也是1磅， 這意味著它能裝入背包！ 因此這個(gè)單元格包含吉他， 價(jià)值為1500美元。 來看下一個(gè)單元格，這個(gè)單元格表示背包的容量為2磅， 完全能夠裝下吉他！這行的其他的單元格也是如此，因?yàn)槟隳壳爸荒馨鸭b入背包，其他兩種商品還未出現(xiàn)，所以第一行變成下圖：

image.png

此時(shí)你可能心存疑惑：原來的問題說的是4磅的背包，為何要考慮容量為1磅、2磅等的背包呢？前面說過，動(dòng)態(tài)規(guī)劃從小問題著手，逐步解決大問題。這里解決的子問題將幫助你解決大問題。

音響行

現(xiàn)在來到第二行，在每一行，可偷的商品都是當(dāng)前行的商品和之前各行的商品。因此，當(dāng)前你已經(jīng)解鎖了音響和吉他，但是筆記本電腦還未解鎖?，F(xiàn)在來看第一個(gè)單元格，它表示容量為1磅的背包。 在此之前， 可裝入1磅背包的商品的最大價(jià)值為1500美元。 背包的容量為1磅， 能裝下音響嗎？ 音響太重了， 裝不下！ 由于容量1磅的背包裝不下音響， 因此最大價(jià)值依然是1500美元。 接下來的兩個(gè)單元格的情況與此相同。

image.png

現(xiàn)在來到了第四個(gè)單元格，也就是說背包容量為4磅，終于能裝下音響，由于音響的價(jià)值為3000美元，比1500美元的吉他值錢多了，所以還是偷音響吧。

image.png

筆記本電腦行

下面以同樣的方式處理筆記本電腦。 筆記本電腦重3磅， 沒法將其裝入容量為1磅或2磅的背包， 因此前兩個(gè)單元格的最大價(jià)值還是1500美元。

image.png

對于容量為3磅的背包， 原來的最大價(jià)值為1500美元， 但現(xiàn)在你可選擇盜竊價(jià)值2000美元的筆記本電腦而不是吉他， 這樣新的最大價(jià)值將為2000美元！

image.png

現(xiàn)在來到這個(gè)問題最關(guān)鍵的單元格，對于容量為4磅的背包，當(dāng)前的最大價(jià)值為3000美元， 你可不偷音響， 而偷筆記本電腦， 但它只值2000美元。但是筆記本電腦的重量只有3磅， 背包還有1磅的容量沒用！ 在1磅的容量中， 可裝入的商品的最大價(jià)值之前計(jì)算過。根據(jù)之前計(jì)算的最大價(jià)值可知， 在1磅的容量中可裝入吉他， 價(jià)值1500美元。于是有了下面的比較：

image.png

于是我們得到了最終的結(jié)果：

image.png

4.背包問題FAQ:

• 增加第四件商品iphone，2000美元，1磅，要重新執(zhí)行前面的計(jì)算么？
  答案：不需要，再增加一行計(jì)算結(jié)果即可。

• 沿著一列往下走時(shí)， 最大價(jià)值有可能降低嗎？
  答案： 不可能。 每次迭代時(shí)， 你都存儲(chǔ)當(dāng)前的最大價(jià)值。 最大價(jià)值不可能比以前低！

• 行的排列順序發(fā)生變化時(shí)結(jié)果將如何變化？
  答案：沒有變化。 也就是說， 各行的排列順序無關(guān)緊要。

• 可以逐列而不是逐行填充網(wǎng)格嗎？
  答案：就這個(gè)問題而言， 這沒有任何影響， 但對于其他問題， 可能有影響。

• 增加一件更小的商品將如何呢？
  答案：單元格的按最小商品的重量劃分。

• 可以偷商品的一部分嗎？
  答案：沒法處理。 使用動(dòng)態(tài)規(guī)劃時(shí)， 要么考慮拿走整件商品， 要么考慮不拿， 而沒法判斷該不該拿走商品的一部分。但使用貪婪算法可輕松地處理這種情況！ 首先， 盡可能多地拿價(jià)值最高的商品； 如果拿光了， 再盡可能多地拿價(jià)值次高的商品， 以此類推。

• 動(dòng)態(tài)規(guī)劃可以處理相互依賴的情況嗎？
  答案： 沒辦法建模。 動(dòng)態(tài)規(guī)劃功能強(qiáng)大， 它能夠解決子問題并使用這些答案來解決大問題。 但僅當(dāng)每個(gè)子問題都是離散的， 即不依賴于其他子問題時(shí)， 動(dòng)態(tài)規(guī)劃才管用 。
  計(jì)算最終的解時(shí)會(huì)涉及兩個(gè)以上的子背包嗎？
  答案：根據(jù)動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)， 最多只需合并兩個(gè)子背包， 即根本不會(huì)涉及兩個(gè)以上的子背包。 不過這些子背包可能又包含子背包。

• 最優(yōu)解可能導(dǎo)致背包沒裝滿嗎？
  答案：完全可能。

5.動(dòng)態(tài)規(guī)劃的啟發(fā)

動(dòng)態(tài)規(guī)劃可幫助你在給定約束條件下找到最優(yōu)解。 在背包問題中，你必須在背包容量給定的情況下， 偷到價(jià)值最高的商品。

在問題可分解為彼此獨(dú)立且離散的子問題時(shí)， 就可使用動(dòng)態(tài)規(guī)劃來解決。要設(shè)計(jì)出動(dòng)態(tài)規(guī)劃解決方案可能很難， 這正是本節(jié)要介紹的。 下面是一些通用的小貼士。

• 每種動(dòng)態(tài)規(guī)劃解決方案都涉及網(wǎng)格。
• 單元格中的值通常就是你要優(yōu)化的值。 在前面的背包問題中， 單元格的值為商品的價(jià)值。
• 每個(gè)單元格都是一個(gè)子問題， 因此你應(yīng)考慮如何將問題分成子問題， 這有助于你找出網(wǎng)格的坐標(biāo)軸。

6.小結(jié)

• 需要在給定約束條件下優(yōu)化某種指標(biāo)時(shí)， 動(dòng)態(tài)規(guī)劃很有用。
• 問題可分解為離散子問題時(shí)， 可使用動(dòng)態(tài)規(guī)劃來解決。
• 每種動(dòng)態(tài)規(guī)劃解決方案都涉及網(wǎng)格。
• 單元格中的值通常就是你要優(yōu)化的值。
• 每個(gè)單元格都是一個(gè)子問題， 因此你需要考慮如何將問題分解為子問題。
• 沒有放之四海皆準(zhǔn)的計(jì)算動(dòng)態(tài)規(guī)劃解決方案的公式。

四、參考知乎 如何理解動(dòng)態(tài)規(guī)劃？

入門動(dòng)態(tài)規(guī)劃第一條：切忌望文生義，切忌用名字反推算法！如果我來命名，可能會(huì)取：分步規(guī)劃，分步存儲(chǔ)法， 遞推存儲(chǔ)法，數(shù)列遞推法，狀態(tài)轉(zhuǎn)移法.....但我就是想不出動(dòng)態(tài)規(guī)劃啊。

1.能用動(dòng)態(tài)規(guī)劃解決的問題

如果一個(gè)問題滿足以下兩點(diǎn)，那么它就能用動(dòng)態(tài)規(guī)劃解決。

(1).問題的答案依賴于問題的規(guī)模，也就是問題的所有答案構(gòu)成了一個(gè)數(shù)列。舉個(gè)簡單的例子，1個(gè)人有2條腿，2個(gè)人有4條腿，...， n 個(gè)人有多少條腿？答案是 2n 條腿。這里的 2n 是問題的答案， n 則是問題的規(guī)模，顯然問題的答案是依賴于問題的規(guī)模的。答案是因變量，問題規(guī)模是自變量。因此，問題在所有規(guī)模下的答案可以構(gòu)成一個(gè)數(shù)列 (f(1),f(2),...,f(n)) ，比如剛剛“數(shù)腿”的例子就構(gòu)成了間隔為2的等差數(shù)列 (0,2,4,...,2n) 。

(2).大規(guī)模問題的答案可以由小規(guī)模問題的答案遞推得到，也就是 f(n) 的值可以由 {f(i)|i<n} 中的個(gè)別求得。還是剛剛“數(shù)腿”的例子，顯然 f(n) 可以基于 f(n-1) 求得： f(n)=f(n-1)+2 。

2.適合用動(dòng)態(tài)規(guī)劃解決的問題

能用動(dòng)態(tài)規(guī)劃解決，不代表適合用。比如剛剛的“數(shù)腿”例子，你可以寫成 f(n)=2n 的顯式表達(dá)式形式，那么殺雞就不必用牛刀了。但是，在許多場景， f(n) 的顯式式子是不易得到的，大多數(shù)情況下甚至無法得到，動(dòng)態(tài)規(guī)劃的魅力就出來了。

3.應(yīng)用動(dòng)態(tài)規(guī)劃——將動(dòng)態(tài)規(guī)劃拆分成三個(gè)子目標(biāo)

當(dāng)要應(yīng)用動(dòng)態(tài)規(guī)劃來解決問題時(shí)，歸根結(jié)底就是想辦法完成以下三個(gè)關(guān)鍵目標(biāo)。

(1).建立狀態(tài)轉(zhuǎn)移方程
這一步是最難的，大部分人都被卡在這里。這一步?jīng)]太多的規(guī)律可說，只需抓住一個(gè)思維：當(dāng)做已經(jīng)知道f(1) ~f(n-1) 的值，然后想辦法利用它們求得 f(n) 。在“數(shù)腿”的例子中，狀態(tài)轉(zhuǎn)移方程即為f(n)=f(n-1)+2 。

(2).緩存并復(fù)用以往結(jié)果
這一步不難，但是很重要。如果沒有合適地處理，很有可能就是指數(shù)和線性時(shí)間復(fù)雜度的區(qū)別。假設(shè)在“數(shù)腿”的例子中，我們不能用顯式方程，只能用狀態(tài)轉(zhuǎn)移方程來解。如果現(xiàn)在 f(100) 未知，但是剛剛求解過一次 f(99) 。如果不將其緩存起來，那么求 f(100) 時(shí)，我們就必須花100次加法運(yùn)算重新獲取。但是如果剛剛緩存過，只需復(fù)用這個(gè)子結(jié)果，那么將只需一次加法運(yùn)算即可。

(3).按順序從小往大算
這里的“小”和“大”對應(yīng)的是問題的規(guī)模，在這里也就是我們要從 f(0) , f(1) , ... 到f(n) 依次順序計(jì)算。這一點(diǎn)在“數(shù)腿”的例子來看，似乎顯而易見，因?yàn)闋顟B(tài)方程基本限制了你只能從小到大一步步遞推出最終的結(jié)果（假設(shè)我們?nèi)匀徊荒苡蔑@式方程）。然而當(dāng)問題復(fù)雜起來的時(shí)候，你有可能亂了套，所以必須記住這也是目標(biāo)之一。

4.高中數(shù)列題的魔改版

看到這里，你可能會(huì)覺得怎么跟高中的數(shù)列題那么像？？其實(shí)在我看來這就是高中數(shù)列題的魔改版。

高中的題一般需先推導(dǎo)出狀態(tài)轉(zhuǎn)移方程，再據(jù)此推導(dǎo)出顯式表達(dá)式（在高中時(shí)代稱為通項(xiàng)公式）。然而，動(dòng)態(tài)規(guī)劃是要我們在推導(dǎo)出狀態(tài)轉(zhuǎn)移方程后，根據(jù)狀態(tài)轉(zhuǎn)移方程用計(jì)算機(jī)暴力求解出來。顯式表達(dá)式？在動(dòng)態(tài)規(guī)劃中是不存在的！

就是因?yàn)橐┝τ?jì)算，所以前面說的目標(biāo)有兩個(gè)是涉及到代碼層面上：

• 緩存中間結(jié)果：也就是搞個(gè)數(shù)組之類的變量記錄中間結(jié)果。
• 按順序從小往大算：也就是搞個(gè)for循環(huán)依次計(jì)算。

5.原文有3個(gè)例子，這里只引用第1個(gè)

斐波那契數(shù)列（簡單）

斐波那契數(shù)列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……
它遵循這樣的規(guī)律：當(dāng)前值為前兩個(gè)值的和。
那么第 n 個(gè)值為多少？
首先，我們可以很容易得到狀態(tài)轉(zhuǎn)移方程： f(n)=f(n-1)+f(n-2) 。接下來我們用兩種方法來做：

(1)簡單遞歸(反例)

def fib(n):
    if n < 2:
        return n
    else:
        return fib(n-1) + fib(n-2)
    
if __name__ == '__main__':
    result = fib(100)  
# 你等到天荒地老，它還沒有執(zhí)行完

如上所示，代碼簡單易懂，然而這代碼卻極其低效。先不說這種遞歸的方式造成棧空間的極大浪費(fèi)，就僅僅是該算法的時(shí)間復(fù)雜度已經(jīng)屬于 O(2^n) 了。指數(shù)級(jí)別時(shí)間復(fù)雜度的算法跟不能用沒啥區(qū)別！

為什么是指數(shù)時(shí)間復(fù)雜度？圖1通過展示求解 f(6) 的過程說明了其原因。如圖，隨著遞歸的深入，計(jì)算任務(wù)不斷地翻倍！

圖1 簡單遞歸的執(zhí)行過程

(2).動(dòng)態(tài)規(guī)劃

def fib(n):
    
    results = list(range(n+1)) # 用于緩存以往結(jié)果，以便復(fù)用（目標(biāo)2）
    
    for i in range(n+1):  # 按順序從小往大算（目標(biāo)3）
        if i < 2:
            results[i] = i
        else:
            # 使用狀態(tài)轉(zhuǎn)移方程（目標(biāo)1），同時(shí)復(fù)用以往結(jié)果（目標(biāo)2）
            results[i] = results[i-1] + results[i-2] 
     
    return results[-1]
    
if __name__ == '__main__':
    result = fib(100)  
    # 秒算，result為：354224848179261915075

如上代碼，針對動(dòng)態(tài)規(guī)劃的三個(gè)子目標(biāo)，都很好地實(shí)現(xiàn)了（參考備注），具體為：

目標(biāo)1，建立狀態(tài)轉(zhuǎn)移方程（完成）。也就是前面的 f(n)=f(n-1)+f(n-2) 。
目標(biāo)2，緩存并復(fù)用以往結(jié)果（完成）。圖1的簡單遞歸存在大量的重復(fù)任務(wù)。在線性規(guī)劃解法中，我們把結(jié)果緩存在results列表，同時(shí)在results[i] = results[i-1] + results[i-2]中進(jìn)行了復(fù)用。這相當(dāng)于我們只需完成圖2中紅色部分的計(jì)算任務(wù)即可，時(shí)間復(fù)雜度瞬間降為 O(n) 。

圖2 線性規(guī)劃通過緩存與復(fù)用機(jī)制將計(jì)算規(guī)?？s小到紅色部分

目標(biāo)3，按順序從小往大算（完成）。for循環(huán)實(shí)現(xiàn)了從0到 n 的順序求解，讓問題按著從小規(guī)模往大規(guī)模求解的順序走。

5.【算法-動(dòng)態(tài)規(guī)劃】-最大子段和

動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解為若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適用與動(dòng)態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨(dú)立的。
分治法的基本思想是將一個(gè)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題，這些子問題相互獨(dú)立且與原問題相同。遞歸的求解這些子問題，然后將各子問題的解合并得到原問題的解。
如果用分治法求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次。如果我們能夠保存已解決的子問題的答案，而在需要的時(shí)再找出已求得的答案這樣就可以避免大量的重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。為了達(dá)到此目的，可以用一個(gè)表來記錄所有已經(jīng)解決的子問題的答案。不管該子問題以后是否被用到，只要它被計(jì)算過，就將其結(jié)果填入表中。這就是動(dòng)態(tài)規(guī)劃法的基本思想。

問題描述：給定由n個(gè)正數(shù)（可能為負(fù)整數(shù)）組成的序列a1,a2,...,an,求該序列形如的子段和的最大值，當(dāng)所有正數(shù)均為負(fù)整數(shù)時(shí)定義其最大字段和為0。
比如-2,11,-4,13,-5.-2，最大字段和是11+(-4)+13=20;6，-1，5，4，-7，其最大子段和為 6+(-1)+5+4

（1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征

由b[j]的定義易知，當(dāng)b[j-1]>0時(shí)b[j]=b[j-1]+a[j],否則b[j]=a[j]

（2）遞歸地定義最優(yōu)值。

b[j]=max{b[j-1]+a[j],a[j]},1<=j<=n

（3）以自底向上的方式計(jì)算出最優(yōu)值。

public class MaxSumClass3{
    public static int MaxSum(int n,int[] a){
        int sum=0,b=0;
        for(int i=1;i<=n;i++){
            if(b<0)b=a[i];
            else b=b+a[i];
            if(b>sum)
                sum=b;
        }
        return sum;
    }
    public static void main(String[] args){
        int n=6;
        int[] a={0,-2,11,-4,13,-5,-2};
        System.out.println(MaxSum(n,a));
    }
}