魔幻的 2020 讓我們懷疑人生是否存在最優解？我們某個時間的決策究竟是否正确？曆史不能改變，但卻會重演，我們究竟要從過去中學到什麼呢？
讓我們一起從動态規劃中，來找尋這些問題的答案吧～
（咳咳，今天開始回歸算法系列，來聊一聊之前的算法文章中沒有講到的内容。
動态規劃（Dynamic Programic，簡稱 DP）是一種求解最優解的方法，它是一種特殊的分治思想，利用它可以實作時間複雜度的優化，有時也可以進行空間複雜度的優化，有時是需要更多的空間的（相比其他方法）。
dynamic 是動态的意思，也就是變化的，programing 可以了解為方程（我瞎說的），結合起來就是動态規劃是用狀态轉移方程來求得最優解的算法。
在解釋動态規劃的時候，我們順便理一理和它相關的兩種思想——分治和貪心算法。
分治是把大問題分解成若幹個子問題，這樣的能分解性質就是最優子結構的。
最簡單的例子就是小明在解決問題 A 的時候，發現問題 A 是由問題 B 和 C 一起組成的，是以他想要解決問題 A，就需要把 B、C 一起去解決。
動态規劃是分治法的特例。
動态規劃比分治法多了一種，就是重疊的子問題。
什麼是重疊的子問題呢？舉個例子來講，可愛的小明遇到了一個可愛的問題，那就是問題 A，但是在前面需要解決一連串的問題，我們用A1，A2，A3，A4 ... A來表示，在解決A1之後會用它的解去解決類似的問題A2，
然後再去解決A3，最終再去解決 A，這就是重疊的子問題的典型代表。（下面的例題還會解釋這個概念）
貪心比動态規劃更加的特殊，它還需要問題滿足另外一個性質——貪心選擇性質，每次都可以把原問題分解成為一個子問題。
實際上再用動規的例子來說明貪心，在解決A1，A2，A3，A4 ... A的時候，他發現解決不光有一種重疊子問題的性質在裡面，更有趣的是，解決A1需要一種特殊的規則。
例如小明現在在玩電腦遊戲，而電腦遊戲的最終目的是到達A，而他又發現，隻要一直往右邊走就能到達最終的目的地了。這就是一種貪心的算法，在每次往右邊走，就是一種特殊的規則，而走到目的地A需要很多重複的子問題，也即每次活動一個機關。
其實在很久之前我寫的一篇文章中，以斐波那契數列這道基本題為例，詳細闡述了從遞歸到 DP 的優化方法和思路，以及簡單題的不簡單的答法，大家不妨先去複習一下：
這才是面試官想聽的：從遞歸到 DP 的優化
然後我們再來看看一般的動态規劃解題思路。
回到動态規劃，這裡有四個基本的概念：
state（狀态表示）
function（轉移方程）
initial（初始化）
final state（最終的狀态）
在剛開始的時候，我們首先需要建構一個存儲資料的表格，一般是數組或者矩陣，然後設定好每一個格子到下一個格子需要的轉移方程。
然後去執行重複的步驟，從初始化的狀态一直計算到最終需要的狀态。
回到小明的例子，剛開始的時候小明需要确定一個 state（A0代表的是什麼），然後找到A0與A1之間的關系，從初始化開始一直計算到最終的狀态。
接下來，我們以 Leetcode 120 來詳細的講解這個算法。
現在我們來分析一下這個題目，首先我們分析一下為什麼它是一個動态規劃的問題。
題目是要找到一種路徑的和，這種路徑和是要最小的，也就是求一個最優解。
因為這是路徑，我們就是在每一層裡面選擇一個合适的數字，然後連成一個路徑，在這道題目裡面，最小的路徑是2-3-5-1，在第一層挑了2，在第二層挑了3。也就是說總的問題拆分成了每一層的問題，而每一層之間都有一種依賴性在裡面，例如第二層選擇了3之後隻能在6,5之中選擇一個，不能跳到7，這就是重疊子問題。
我們用f[i][j]表示從三角形頂部走到位置 [i][j] 的最小路徑和。這裡的位置 i, j 指的是三角形中第 i 行第 j 列的位置。
由于隻能是從一個節點到相鄰的兩個節點（樹），是以要想走到位置 [i][j]，上一步就隻能在位置 [i-1][j-1] 或者位置 [i-1][j]。
我們在這兩個位置中選擇一個路徑和較小的來進行轉移，狀态轉移方程為：
f[i][j]=min(f[i−1][j−1],f[i−1][j])+c[i][j]，
其中 c[i][j] 指的是triangle[i][j]的數值。
當設定完通項方程之後，我們還需要設定一些特殊的轉化方程：
當靠近左邊界時，也就是 j = 0 時，于是沒有f[i-1][j−1]這一項 ，狀态轉移方程變為：
f[i][0]=f[i−1][0]+c[i][0]
當靠近右邊界時，我們直接用上一層斜上角位置的數值進行計算：
f[i][i]=f[i−1][i−1]+c[i][i]
最終，我們隻需要在 dp 三角形的最後一行找到最小值就可以了。
那麼初始的狀态是什麼呢？
實際上就是剛開始的時候設定 dp 的第一個機關的數值為cp[0][0]，也即是dp[0][0] = c[0][0]。
狀态轉換圖如下所示：
代碼如下：
下面來分析這個問題的時間複雜度以及空間複雜度，一般來說空間複雜度是就是 DP 表格的大小。
在這道問題中是 O(n^2)，而對于時間複雜度來說，就是整個 dp 的周遊次數，而在這個問題中我們隻進行了一次周遊，也即一個矩陣的周遊，是以是O(n^2)。
而如果想要優化到 O(n)，我們需要怎麼做呢？
實際上這個就涉及到了一種狀态壓縮的方法，也即壓縮這個狀态表。
那麼怎麼去壓縮呢？
這個問題比較簡單，因為dp[i][j]僅僅與上一層的狀态有關，是以說與前兩層的是沒有任何關系的，是以我們不必存儲這些無關的狀态。
實際上最簡單的狀态壓縮就是保留好前兩個狀态即可，例如在計算第四行的時候，保留第三行以及第二行的狀态表，然後交替的進行更新就可以啦。
這個的空間複雜度是 O(2n)，能不能壓縮成嚴格意義上的O(n)呢？
那麼再往後是否還能夠進行狀态的壓縮呢？
答案是可以的，我們可以再想一種方程然後達到最優的空間複雜度的目标。
當我們在計算位置 [i][j] 時，f[j+1] 到 f[i] 已經是第 i 行的值，而 f[0] 到 f[j] 仍然是第 i-1 行的值。
此時我們直接通過 f[j] = min(f[j−1], f[j]) + c[i][j]來計算，但是這個時候我們需要j 是倒着周遊的，因為這樣才不會影響之前記錄下的狀态。
如果從 1 開始，那麼計算 2 的時候就會用到新的 1 的數值而不是上一層 1 的數值。
方法 1 有點繞，但如果自下向上來了解，就會變得很簡單，這個方法也叫 bottom-up，方法 1 則是 top-down。
從結果出發，這個問題是一個發散三角樹的問題，從最後一行出發，然後每一行每一行的進行遞推，那麼第一行就是最終的結果了。
舉個最簡單的例子：
如果從最底下往上出發，實際上找最小值方法的規律很容易找到，那就是在第二行[1， 2]裡面選擇一個就可以了，因為他們兩個都要走到根節點。
也就是在下一行的兩個數裡面取個小的就行了，那麼結果就是第一行的數值。
我們先用二維的轉移矩陣來解釋這個問題，用這種方法也不需要考慮方法 1 裡面的邊界條件了：
dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + c[i][j]
那麼在進行狀态壓縮的時候，我們該怎麼去做呢？
實際上就是隻用一個狀态表來表示所有的。
因為隻是和上一個狀态相關，是以說可以表示成如下的形式：
dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]，
我們隻用 j 來代表目前的狀态，然後最終輸出dp[0]即可。
總結
以上就是動态規劃解題方法的粗淺介紹，總的來說，我們需要注意動态規劃的這麼幾件事情。
确定是否需要用動态規劃；
确定動态規劃的四個部分；
寫代碼。
實際上難點就是轉移方程，這個确實需要大量的積累才能夠在面試的時候看穿，甚至有些題沒見過的話就是想不出來的。
但是沒見過就做不出來的題面試一般也不會考，是以大家也不用太擔心，重點還是掌握方法，舉一反三。
接下來我也會歸納總結一些動态規劃的常見題型，和大家一起探索最優解。
更多算法文章，建議收藏這個連結：
齊姐聊算法
我是小齊，後端開發工程師，坐标紐約，曾在投行做 Quant，後加入科技公司 FLAG 中的一家。
業餘時間打理公粽号【NYCSDE】，更新略少，幹貨很多，建議加個星标防止錯過。