# Dynamic Programming - 動態規劃 動態規劃是一種「分治」的思想，通俗一點來說就是「大事化小，小事化無」的藝術。在將大問題化解為小問題的「分治」過程中，保存對這些小問題已經處理好的結果，并供后面處理更大規模的問題時直接使用這些結果。嗯，感覺講了和沒講一樣，還是不會使用動規的思想解題... 下面看看知乎上的熊大大對動規比較「正經」的描述。 > 動態規劃是通過拆分問題，定義問題狀態和狀態之間的關系，使得問題能夠以遞推（或者說分治）的方式去解決。 以上定義言簡意賅，可直接用于實戰指導，不愧是參加過NOI的。 動規的思想雖然好理解，但是要真正活用起來就需要下點功夫了。建議看看下面知乎上的回答。 動態規劃最重要的兩個要點： 1. 狀態(狀態不太好找，可先從轉化方程入手分析) 1. 狀態間的轉化方程(從題目的隱含條件出發尋找遞推關系) 其他的要點則是如初始化狀態的確定(由狀態和轉化方程得知)，需要的結果(狀態轉移的終點) 動態規劃問題中一般從以下四個角度考慮： 1. 狀態(State) 1. 狀態間的轉移方程(Function) 1. 狀態的初始化(Initialization) 1. 返回結果(Answer) 動規適用的情形： 1. 最大值/最小值 1. 有無可行解 1. 求方案個數(如果需要列出所有方案，則一定不是動規，因為全部方案為指數級別復雜度，所有方案需要列出時往往用遞歸) 1. 給出的數據不可隨便調整位置 ### 單序列([DP_Sequence](# "單序列動態規劃，通常使用 f[i] 表示前i個位置/數字/字母... 使用 f[n-1] 表示最后返回結果。")) 單序列動態規劃的狀態通常定義為：數組前 i 個位置, 數字, 字母 或者 以第i個為... 返回結果通常為數組的最后一個元素。 按照動態規劃的四要素，此類題可從以下四個角度分析。 1. State: f[i] 前i個位置/數字/字母... 1. Function: f[i] = f[i-1]... 找遞推關系 1. Initialization: 根據題意進行必要的初始化 1. Answer: f[n-1] ### 雙序列([DP_Two_Sequence](# "一般有兩個數組或者兩個字符串，計算其匹配關系. 通常可用 `f[i][j]`表示第一個數組的前 i 位和第二個數組的前 j 位的關系。")) 一般有兩個數組或者兩個字符串，計算其匹配關系。雙序列中常用二維數組表示狀態轉移關系，但往往可以使用滾動數組的方式對空間復雜度進行優化。舉個例子，以題 [Distinct Subsequences](http://algorithm.yuanbin.me/zh-cn/dynamic_programming/distinct_subsequences.html) 為例，狀態轉移方程如下： ~~~ f[i+1][j+1] = f[i][j+1] + f[i][j] (if S[i] == T[j]) f[i+1][j+1] = f[i][j+1] (if S[i] != T[j]) ~~~ 從以上轉移方程可以看出 `f[i+1][*]` 只與其前一個狀態 `f[i][*]` 有關，而對于 `f[*][j]` 來說則基于當前索引又與前一個索引有關，故我們以遞推的方式省略第一維的空間，并以第一維作為外循環，內循環為 j, 由遞推關系可知在使用滾動數組時，若內循環 j 仍然從小到大遍歷，那么對于 `f[j+1]` 來說它得到的 `f[j]` 則是當前一輪(`f[i+1][j]`)的值，并不是需要的 `f[i][j]` 的值。所以若想得到上一輪的結果，必須在內循環使用逆推的方式進行。文字表述比較模糊，可以自行畫一個二維矩陣的轉移矩陣來分析，認識到這一點非常重要。 小結一下，使用滾動數組的核心在于： 1. 狀態轉移矩陣中只能取 `f[i+1][*]` 和 `f[i][*]`, 這是使用滾動數組的前提。 1. 外循環使用 i, 內循環使用 j 并同時使用逆推，這是滾動數組使用的具體實踐。 代碼如下： ~~~ public class Solution { /** * @param S, T: Two string. * @return: Count the number of distinct subsequences */ public int numDistinct(String S, String T) { if (S == null || T == null) return 0; if (S.length() < T.length()) return 0; if (T.length() == 0) return 1; int[] f = new int[T.length() + 1]; f[0] = 1; for (int i = 0; i < S.length(); i++) { for (int j = T.length() - 1; j >= 0; j--) { if (S.charAt(i) == T.charAt(j)) { f[j + 1] += f[j]; } } } return f[T.length()]; } } ~~~ 紙上得來終覺淺，絕知此事要躬行。光說不練假把戲，下面就來幾道DP的題練練手。 ### Reference 1. [什么是動態規劃？動態規劃的意義是什么？ - 知乎](http://www.zhihu.com/question/23995189) - 熊大大和王勐的回答值得細看，適合作為動態規劃的科普和入門。維基百科上對動態規劃的描述感覺太過學術。 1. [動態規劃：從新手到專家](http://www.hawstein.com/posts/dp-novice-to-advanced.html) - Topcoder上的一篇譯作。