動態規劃演算法視頻

Ⅰ 演算法題套路總結（三）——動態規劃

前兩篇我總結了鏈表和二分查找題目的一些套路，這篇文章來講講動態規劃。動態規劃從我高中開始參加NOIP起就一直是令我比較害怕的題型，除了能一眼看出來轉移方程的題目，大部分動態規劃都不太會做。加上後來ACM更為令人頭禿的動態規劃，很多題解看了之後，我根本就不相信自己能夠想出來這種解法，看著大佬們談笑間還加一些常數優化，一度懷疑自己的智商。以前一直覺得動態規劃是給大佬准備的，所以刻意地沒有去攻克它，主要也是沒有信心。但是後來慢慢的，我再做LC的時候，發現很多DP的題目我自己慢慢能夠推出轉移方程了，而且似乎也沒那麼難。我一直在思考，到底是我變強了，還是因為LC的題目相比ACM或者NOI太簡單了。其實主要還是後者，但是同時我也發現，動態規劃其實是有套路的，我以前方法不對，總結太少。
主要就是，站在出題人的角度，他幾乎不太可能完全憑空想出一個新的DP模型，因為動態規劃畢竟要滿足：

因此，能夠利用DP來解決的問題實際上是有限的，大部分題目都是針對現有的模型的一些變種，改改題目描述，或者加點限制條件。所以要想攻克DP題目，最根本的就是要充分理解幾個常見的DP模型。而要充分理解常見經典DP模型，就需要通過大量的做題和總結，而且二者不可偏廢。通過做題進行思考和量的積累，通過總結加深理解和融會貫通進而完成質的提升。

動態規劃是求解一個最優化問題，而最核心的思想就是：

解一道DP題目，先問自己幾個問題：

當然以上內容看起來比較抽象，雖然它深刻地揭露了動態規劃的本質，但是如果臨場要去想明白這些問題，還是有些難度。如果只是針對比賽和面試，就像前面說的，DP題型是有限的。只要刷的題目足夠多，總結出幾個經典模型，剩下的都是些變種+優化而已。

一般來說，動態規劃可以分成4個大類:

線性DP就是階段非常線性直觀的模型，比如：最長（上升|下降）序列，最長公共子序列(LCS)等，也有一些簡單的遞推，甚至都算不上是 經典模型 。

最長上升序列是一個非常經典的線性模型。說它是個模型，是因為它是一類題的代表，很多題目都只是換個說法，或者要求在這基礎上進一步優化而已。最長上升序列最基礎的轉移方程就是 f[i] = max{f[j]}+1 (a[i] > a[j]) , f[i] 表示一定要以 a[i] 結尾的序列，最長長度是多少。很顯然就是在前面找到一個最大的 f[j] 同時滿足 a[j]<a[i] 。因此是 N^2 的時間復雜度和N的空間復雜度。這種方法是最樸素直觀的，一定要理解。它非常簡單，因此很少有題目直接能夠這么做。大部分相關題目需要進一步優化，也就是有名的單調隊列優化，能夠把復雜度優化到nlogn。

說單調隊列優化之前必須明白一個貪心策略。因為要求的是最長上升序列，那麼很顯然長度為k的上升序列的最大值（最後一個數）越小越好，這樣後面的數才有更大的概率比它大。如果我們記錄下來不同長度的上升序列的最後一個數能達到的最小值，那麼對於後續每個數t，它要麼能放到某個長度為y的序列之後，組成長度為y+1的上升序列，要麼放到某個長度為x的序列後面，把長度為x+1的序列的最大值替換成t。同時我們可以發現，如果x<y，那麼長度為x序列的最後一個數一定比長度為y的序列最後一個數小。因此這個上升序列我們可以用一個數組來維護（所謂的單調隊列），數組下標就代表序列長度。 opt[i]=t 表示長度為i的上升序列最後一個數最小是t。那麼當我們在面對後續某個數x時，可以對單調隊列opt進行二分，把它插到對應的位置。因此總體復雜度就是NlogN。
相關題目比如：

但是你可以發現，其實這個題型其實變種很有限，吃透了也就那麼回事。所以一定要總結。

最長公共子序列也是線性DP中的一種比較常見的模型。說它是一種「模型」其實有點拔高了，其實它就是一類比較常見的題目。很多題目都是在LCS的基礎上進行簡單的擴展，或者僅僅就是換一個說法而已。
求兩個數組的最長公共子序列，最直觀地做法就是：設f[i][j]表示S[..i]和T[..j]的最長公共子序列，則有:

這個轉移方程也非常好理解，時間復雜度是 N^2 ，空間復雜度也是 N^2 。不過仔細觀察你可以發現，當我們計算第i行時只與i-1和i行有關。因此我們可以利用01滾動來優化空間復雜度為2N。
相關題目：

線性DP除了上述的兩種常見題型，還有很多別的類型，包括背包。我們要努力去嘗試理解這些題目的異同，它們的轉移方程，以及思路，可能的變化，這樣才能更好的應對未知的題目。以下是一些我總結的題型：

最終結果就是max(0, f[n][2]+f[n][4])。
不過實際上你可以發現，由於各個狀態只和前一維有關，且只能由固定的一個狀態轉移過來，因此我們可以省掉一維，只用4個變數來存儲：

剩下的，同123題類似，由於最多進行k次交易，那麼一天就有2k個狀態：第1次買/賣……第k次買/賣，結合123題的優化，我們只需要2k個變數就能存儲這些狀態。因此設f[i×2]為第i次買入的最優值，f[i×2+1]為第i次賣出的最優值：

以上都是對一些常見的線性DP的一些小結，實際上線性DP還有一個重要的題型就是背包。關於背包，有很多相關的講解，我這里就不多說了，推薦大家看看 背包九講 。下一章依然是DP專題，我講總結一些區間DP的題型。大部分區間DP都是hard級的，對於希望提高自己水平的人來說，需要投入更多精力去理解。

Ⅱ 計算機演算法分析考試：動態規劃0-1背包問題，怎麼算

問題描述：
給定n種物品和一背包，物品i的重量是wi，其價值為vi，背包的容量為C。問應如何選擇裝入背包的物品（物品不能分割），使得裝入背包中物品的總價值最大?

抽象描述如下：
x[n]:表示物品的選擇，x[i]=1表示選擇放進物品i到背包中。

Ⅲ Python之動態規劃演算法

動態規劃演算法中是將復雜問題遞歸分解為子問題，通過解決這些子問題來解決復雜問題。與遞歸演算法相比，動態編程減少了堆棧的使用，避免了重復的計算，效率得到顯著提升。

先來看一個簡單的例子，斐波那契數列.

斐波那契數列的定義如下。

斐波那契數列可以很容易地用遞歸演算法實現：

上述代碼，隨著n的增加，計算量呈指數級增長，演算法的時間復雜度是 。

採用動態規劃演算法，通過自下而上的計算數列的值，可以使演算法復雜度減小到 ，代碼如下。

下面我們再看一個復雜一些的例子。

這是小學奧數常見的硬幣問題： 已知有1分，2分，5分三種硬幣數量不限，用這些硬幣湊成為n分錢，那麼一共有多少種組合方法。

我們將硬幣的種類用列表 coins 定義；
將問題定義為一個二維數組 dp，dp[amt][j] 是使用 coins 中前 j+1 種硬幣( coins[0:j+1] )湊成總價amt的組合數。

例如： coins = [1,2,5]

dp[5][1] 就是使用前兩種硬幣 [1,2] 湊成總和為5的組合數。

對於所有的 dp[0][j] 來說，湊成總價為0的情況只有一種，就是所有的硬幣數量都為0。所以對於在有效范圍內任意的j，都有 dp[0][j] 為1。

對於 dp[amt][j] 的計算，也就是使用 coins[0:j+1] 硬幣總價amt的組合數，包含兩種情況計算：

1.當使用第j個硬幣時，有 dp[amt-coins[j]][j] 種情況，即amt減去第j個硬幣幣值，使用前j+1種硬幣的組合數；

2.當不使用第j個硬幣時，有 dp[amt][j-1] 種情況，即使用前j種硬幣湊成amt的組合數；

所以： dp[amt][j] = dp[amt - coins[j]][j]+dp[amt][j-1]

我們最終得到的結果是：dp[amount][-1]

上述分析省略了一些邊界情況。

有了上述的分析，代碼實現就比較簡單了。

動態規劃演算法代碼簡潔，執行效率高。但是與遞歸演算法相比，需要仔細考慮如何分解問題，動態規劃代碼與遞歸調用相比，較難理解。

我把遞歸演算法實現的代碼也附在下面。有興趣的朋友可以比較一下兩種演算法的時間復雜度有多大差別。

上述代碼在Python 3.7運行通過。

Ⅳ 動態規劃怎樣計算最優解和最優值

動態規劃演算法通常用於求解具有某種最優性質的問題，需要最優子結構性質來確定最優策略。
一個最優化策略具有這樣的性質，不論過去狀態和決策如何，對前面的決策所形成的狀態而言，餘下的諸決策必須構成最優策略。簡而言之，一個最優化策略的子策略總是最優的。一個問題滿足最優化原理又稱其具有最優子結構性質。

Ⅳ 動態規劃

動態規劃（Dynamic Programming，DP）是運籌學的一個分支，是求解 決策過程最優化 的過程。20世紀50年代初，美國數學家貝爾曼（R.Bellman）等人在研究多階段決策過程的優化問題時，提出了著名的最優化原理，從而創立了動態規劃。動態規劃的應用極其廣泛，包括工程技術、經濟、工業生產、軍事以及自動化控制等領域，並在背包問題、生產經營問題、資金管理問題、資源分配問題、最短路徑問題和復雜系統可靠性問題等中取得了顯著的效果。

雖然動態規劃主要用於求解以時間劃分階段的動態過程的優化問題，但是一些與時間無關的靜態規劃(如 線性規劃、非線性規劃 )，只要人為地引進時間因素，把它視為多階段決策過程，也可以用動態規劃方法方便地求解。

在現實生活中，有一類活動的過程，由於它的特殊性，可將過程分成若干個互相聯系的階段，在它的每一階段都需要作出決策，從而使整個過程達到最好的活動效果。因此各個階段決策的選取不能任意確定， 它依賴於當前面臨的狀態，又影響以後的發展 。當各個階段決策確定後，就組成一個決策序列，因而也就確定了整個過程的一條活動路線．這種把一個問題看作是一個 前後關聯具有鏈狀結構的多階段過程 就稱為多階段決策過程，這種問題稱為多階段決策問題。在多階段決策問題中，各個階段採取的決策，一般來說是與時間有關的， 決策依賴於當前狀態，又隨即引起狀態的轉移 ，一個決策序列就是在變化的狀態中產生出來的，故有「動態」的含義，稱這種解決多階段決策最優化的過程為動態規劃方法

動態規劃演算法通常用於求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應於一個值，我們希望找到具有最優值的解。 動態規劃演算法與分治法類似 ，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然後從這些子問題的解得到原問題的解。與分治法不同的是， 適合於用動態規劃求解的問題，經分解得到子問題往往不是互相獨立的 。若用分治法來解這類問題，則分解得到的子問題數目太多，有些子問題被重復計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復計算，節省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以後是否被用到，只要它被計算過，就將其結果填入表中。這就是動態規劃法的基本思路。具體的動態規劃演算法多種多樣，但它們具有相同的填表格式。

以一個例子來說明動態規劃的概念(leetcode第5題最長迴文子串)：

在這個例子中，一個字元串如果是迴文子串，那麼去掉頭尾也照樣是迴文子串。而每一個字元都有可能是最長迴文子串的一部分。

上面這個例子使用一個二維數組表示各個階段的狀態，這個二維數組的行是子串的起始位置，列是子串的結束位置。由於j>=i，所以只需要考慮二維數組的主對角線的上半部分，對角線上的值永遠是true。用true表示這個子串是迴文串，false不是迴文串。那麼對於某個固定位置的數組元素來說，它的值依賴於左下角的元素的值。進行填充的時候只能一列一列地進行填充，同一列的元素從上到下依次填充。