動態規劃問題總結

02-24

此文章是同門何健同學所做！請勿轉載 @HanKin

動態規劃hankin2015.github.io

什麼是動態規劃，我們要如何描述它?

動態規劃演算法通常基於一個遞推公式及一個或多個初始狀態。當前子問題的解將由上一次子問題的解推出。使用動態規劃來解題只需要多項式時間複雜度，因此它比回溯法、暴力法等要快許多。

首先，我們要找到某個狀態的最優解，然後在它的幫助下，找到下一個狀態的最優解。

「狀態」用來描述該問題的子問題的解。

遞推、遞歸和迭代

迭代演算法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、適合做重複性操作的特點，讓計算機對一組指令（或一定步驟）進行重複執行，在每次執行這組指令（或這些步驟）時，都從變數的原值推出它的一個新值。

通常情況下，迭代俗稱「循環」。

編程語言中的forforeachwhileloopdo while等都是循環

遞歸與循環：

從理論上說，所有的遞歸函數都可以轉換為迭代函數，反之亦然，然而代價通常都是比較高的。當遞歸次數較多時，內存佔用也會隨之增加。

遞推與遞歸：

從程序上看，遞歸表現為自己調用自己，遞推則沒有這樣的形式。
遞歸是從問題的最終目標出發，逐漸將複雜問題化為簡單問題，最終求得問題。
是逆向的。遞推是從簡單問題出發，一步步的向前發展，最終求得問題。是正向的。
遞歸中，問題的n要求是計算之前就知道的，而遞推可以在計算中確定，不要求計算前就知道n。
一般來說，遞推的效率高於遞歸（當然是遞推可以計算的情況下）。

動態規劃和貪心演算法的區別

相同點

動態規劃和貪心演算法都是一種遞推演算法。

均有局部最優解來推導全局最優解。

不同點

貪心演算法：

貪心演算法中，作出的每步貪心決策都無法改變，因為貪心策略是由上一步的最優解推導下一步的最優解，而上一部之前的最優解則不作保留。
由（1）中的介紹，可以知道貪心法正確的條件是：每一步的最優解一定包含上一步的最優解。

動態規劃演算法：

全局最優解中一定包含某個局部最優解，但不一定包含前一個局部最優解，因此需要記錄之前的所有最優解
動態規劃的關鍵是狀態轉移方程，即如何由以求出的局部最優解來推導全局最優解
邊界條件：即最簡單的，可以直接得出的局部最優解

貪心法的基本思路

從問題的某一個初始解出發逐步逼近給定的目標，以儘可能快的地求得更好的解。當達到某演算法中的某一步不能再繼續前進時，演算法停止。

該演算法存在問題：

不能保證求得的最後解是最佳的；
不能用來求最大或最小解問題；
只能求滿足某些約束條件的可行解的範圍。實現該演算法的過程：
從問題的某一初始解出發；

while 能朝給定總目標前進一步 do 求出可行解的一個解元素；由所有解元素組合成問題的一個可行解。

貪心演算法最經典的例子，給錢問題。

比如中國的貨幣，只看元，有1元2元5元10元20、50、100

如果我要16元，可以拿16個1元，8個2元，但是怎麼最少呢？

如果用貪心算，就是我每一次拿那張可能拿的最大的。

比如16，我第一次拿20拿不起，拿10元，OK，剩下6元，再拿個5元，剩下1元

也就是3張 10、5、1。

每次拿能拿的最大的，就是貪心。

但是一定注意，貪心得到的並不是最優解，也就是說用貪心不一定是拿的最少的張數

貪心只能得到一個比較好的解，而且貪心演算法很好想得到。

再注意，為什麼我們的錢可以用貪心呢？因為我們國家的錢的大小設計，正好可以使得貪心演算法算出來的是最優解（一般是個國家的錢幣都應該這麼設計）。如果設計成別的樣子情況就不同了:

比如某國的錢幣分為 1元3元4元如果要拿6元錢怎麼拿？貪心的話先拿4 再拿兩個1 一共3張錢實際最優呢？兩張3元就夠了。

求最優解的問題，從根本上說是一種對解空間的遍歷。最直接的暴力分析容易得到，最優解的解空間通常都是以指數階增長，因此暴力窮舉都是不可行的。

最優解問題大部分都可以拆分成一個個的子問題，把解空間的遍歷視作對子問題樹的遍歷，則以某種形式對樹整個的遍歷一遍就可以求出最優解，如上面的分析，這是不可行的。

貪心和動態規劃本質上是對子問題樹的一種修剪。兩種演算法要求問題都具有的一個性質就是「子問題最優性」。即，組成最優解的每一個子問題的解，對於這個子問題本身肯定也是最優的。如果以自頂向下的方向看問題樹（原問題作根），則，我們每次只需要向下遍歷代表最優解的子樹就可以保證會得到整體的最優解。形象一點說，可以簡單的用一個值（最優值）代表整個子樹，而不用去求出這個子樹所可能代表的所有值。

動態規劃方法代表了這一類問題的一般解法。我們自底向上（從葉子向根）構造子問題的解，對每一個子樹的根，求出下面每一個葉子的值，並且以其中的最優值作為自身的值，其它的值捨棄。動態規劃的代價就取決於可選擇的數目（樹的叉數）和子問題的的數目（樹的節點數，或者是樹的高度？）。

貪心演算法是動態規劃方法的一個特例。貪心特在，可以證明，每一個子樹的根的值不取決於下面葉子的值，而只取決於當前問題的狀況。換句話說，不需要知道一個節點所有子樹的情況，就可以求出這個節點的值。通常這個值都是對於當前的問題情況下，顯而易見的「最優」情況。因此用「貪心」來描述這個演算法的本質。由於貪心演算法的這個特性，它對解空間樹的遍歷不需要自底向上，而只需要自根開始，選擇最優的路，一直走到底就可以了。這樣，與動態規劃相比，它的代價只取決於子問題的數目，而選擇數目總為1。

動態規劃：從新手到專家

意識到，DP是由上一個狀態解找到下個狀態解，所以一般要去找上一個狀態，如 $-1$ ， $j$ 等等。

問題一

一個序列有 $N$ 個數： $A[1],A[2],…,A[N]$ ，求出最長非降子序列的長度。 (講DP基本都會講到的一個問題LIS：longest increasing subsequence)

狀態： $d[i]$ 表示 $i$ 長度的序列最長非降子序列的長度。

狀態轉移方程： $d[i] = max{1, d[j] + 1}$ ,其中 $j < i, A[j] <= A[i]$ 。

問題二

如果我們有面值為1元、3元和5元的硬幣若干枚，如何用最少的硬幣湊夠11元？ (表面上這道題可以用貪心演算法，但貪心演算法無法保證可以求出解，比如1元換成2元的時候)

狀態： $d[i]$ 表示湊夠i元的最少硬幣個數

狀態轉移方程： $d[i] = min{d[i - vj] + 1}$ ，其中 $i - v_j >= 0$ ， $v_j$ 表示第 $j$ 個硬幣的面值;

問題三

無向圖 $G$ 有 $N$ 個結點 $(1<N<=1000)$ 及一些邊，每一條邊上帶有正的權重值。找到結點1到結點 $N$ 的最短路徑，或者輸出不存在這樣的路徑。

提示：在每一步中，對於那些沒有計算過的結點，及那些已經計算出從結點1到它的最短路徑的結點，如果它們間有邊，則計算從結點1到未計算結點的最短路徑。

狀態： $d[i]$ 表示結點1到達結點i的最短路徑長度。

狀態轉移方程： $d[i] = min{d[i], d[j] + dis[i][j]}$ 。 $2-N$ 的結點初始長度為無窮，每次判斷一個結點的鄰居。

問題四

平面上有 $N＊M$ 個格子，每個格子中放著一定數量的蘋果。你從左上角的格子開始，每一步只能向下走或是向右走，每次走到一個格子上就把格子里的蘋果收集起來，這樣下去，你最多能收集到多少個蘋果。

狀態： $d[i][j]$ 表示在格子 $(i, j)$ 最多能收集到的蘋果數量。

狀態轉移方程： $d[i][j] = max{d[i-1][j] (if i > 0), d[i][j - 1] (if j > 0)} + A[i][j]$ 。

問題五(帶有額外條件的DP問題)

無向圖 $G$ 有 $N$ 個結點，它的邊上帶有正的權重值。你從結點1開始走，並且一開始的時候你身上帶有 $M$ 元錢。如果你經過結點i，那麼你就要花掉 $S[i]$ 元(可以把這想像為收過路費)。如果你沒有足夠的錢，就不能從那個結點經過。在這樣的限制條件下，找到從結點1到結點N的最短路徑。或者輸出該路徑不存在。如果存在多條最短路徑，那麼輸出花錢數量最少的那條。限制： $1<N<=100 ; 0<=M<=100 ;$ 對於每個 $i$ ， $0<=S[i]<=100$ ；正如我們所看到的，如果沒有額外的限制條件(在結點處要收費，費用不足還不給過)

狀態： $d[i][j]$ 表示從開始結點到結點i的最短路徑長度，且剩餘 $j$ 元。

For All Neighbors p of Vertex k:

狀態轉移方程(參考問題三)： $d[p][j - s[p]] = min{d[i][j] + dis[i][p], d[p][j - s[p]]}$ ( $if : j - s[p] >= 0$ 能夠支付費用)

問題六(高級)

給定一個 $M$ 行 $N$ 列的矩陣( $M*N$ 個格子)，每個格子中放著一定數量的蘋果。你從左上角的格子開始，只能向下或向右走，目的地是右下角的格子。你每走過一個格子，就把格子上的蘋果都收集起來。然後你從右下角走回左上角的格子，每次只能向左或是向上走，同樣的，走過一個格子就把裡面的蘋果都收集起來。最後，你再一次從左上角走到右下角，每過一個格子同樣要收集起裡面的蘋果 (如果格子里的蘋果數為0，就不用收集)。求你最多能收集到多少蘋果。

注意：當你經過一個格子時，你要一次性把格子里的蘋果都拿走。

限制條件： $1 < N, M <= 50$ ；每個格子里的蘋果數量是0到1000(包含0和1000)。

我們可以將這3條路徑記為左，中，右路徑。對於兩條相交路徑(如下圖)：

在不影響結果的情況下，我們可以將它們視為兩條不相交的路徑：

這樣一來，我們將得到左，中，右3條路徑。此外，如果我們要得到最優解，路徑之間不能相交(除了左上角和右下角必然會相交的格子)。因此對於每一行 $y$ ( 除了第一行和最後一行)，三條路徑對應的 $x$ 坐標要滿足： $x1[y] < x2[y] < x3[y]$ 。經過這一步的分析，問題的DP解法就進一步地清晰了。讓我們考慮行y，對於每一個 $x1[y-1]$ ， $x2[y-1]$ 和 $x3[y-1]$ ，我們已經找到了能收集到最多蘋果數量的路徑。根據它們，我們能求出行y的最優解。現在我們要做的就是找到從一行移動到下一行的方式。令 $Max[i][j][k]$ 表示到第 $y-1$ 行為止收集到蘋果的最大數量，其中3條路徑分別止於第 $i,j,k$ 列。對於下一行 $y$ ，對每個 $Max[i][j][k]$ 都加上格子 $(y,i)$ ， $(y,j)$ 和 $(y,k)$ 內的蘋果數量。因此，每一步我們都向下移動。我們做了這一步移動之後，還要考慮到，一條路徑是有可能向右移動的。 (對於每一個格子，我們有可能是從它上面向下移動到它，也可能是從它左邊向右移動到它)。為了保證3條路徑互不相交，我們首先要考慮左邊的路徑向右移動的情況，然後是中間，最後是右邊的路徑。為了更好的理解，讓我們來考慮左邊的路徑向右移動的情況，對於每一個可能的 $j,k$ 對 $(j < k)$ ，對每個 $i(i < j)$ ，考慮從位置 $(i-1,j,k)$ 移動到位置 $(i,j,k)$ 。處理完左邊的路徑，再處理中間的路徑，最後處理右邊的路徑。方法都差不多。