Dynamic Programming - 動態規劃

    下面看看知乎上的熊大大對動規比較「正經」的描述。

    以上定義言簡意賅，可直接用於實戰指導，不愧是參加過NOI的。

    動規的思想雖然好理解，但是要真正活用起來就需要下點功夫了。建議看看下面知乎上的回答。

    1. 狀態(狀態不太好找，可先從轉化方程入手分析)
    2. 狀態間的轉化方程(從題目的隱含條件出發尋找遞推關係)

    其他的要點則是如初始化狀態的確定(由狀態和轉化方程得知)，需要的結果(狀態轉移的終點)

    動態規劃問題中一般從以下四個角度考慮：

    1. 狀態(State)
    2. 狀態間的轉移方程(Function)
    3. 狀態的初始化(Initialization)
    4. 返回結果(Answer)

    動規適用的情形：

    1. 最大值/最小值
    2. 有無可行解
    3. 求方案個數(如果需要列出所有方案，則一定不是動規，因爲全部方案爲指數級別複雜度，所有方案需要列出時往往用遞歸)
    4. 給出的數據不可隨便調整位置

    單序列動態規劃的狀態通常定義爲：陣列前 i 個位置, 數字, 字母 或者 以第i個爲… 返回結果通常爲陣列的最後一個元素。

    1. State: f[i] 前i個位置/數字/字母…
    2. Initialization: 根據題意進行必要的初始化
    3. Answer: f[n-1]

    雙序列(DP_Two_Sequence)

    一般有兩個陣列或者兩個字符串，計算其匹配關係。雙序列中常用二維陣列表示狀態轉移關係，但往往可以使用滾動陣列的方式對空間複雜度進行優化。舉個例子，以題 爲例，狀態轉移方程如下：

    從以上轉移方程可以看出 只與其前一個狀態 f[i][*] 有關，而對於 f[*][j] 來說則基於當前索引又與前一個索引有關，故我們以遞推的方式省略第一維的空間，並以第一維作爲外循環，內循環爲 j, 由遞推關係可知在使用滾動陣列時，若內循環 j 仍然從小到大遍歷，那麼對於 f[j+1] 來說它得到的 f[j] 則是當前一輪(f[i+1][j])的值，並不是需要的 f[i][j] 的值。所以若想得到上一輪的結果，必須在內循環使用逆推的方式進行。文字表述比較模糊，可以自行畫一個二維矩陣的轉移矩陣來分析，認識到這一點非常重要。

    小結一下，使用滾動陣列的核心在於：

    1. 狀態轉移矩陣中只能取 f[i+1][*] 和 f[i][*], 這是使用滾動陣列的前提。
    2. 外循環使用 i, 內循環使用 j 並同時使用逆推，這是滾動陣列使用的具體實踐。

    程式碼如下：

    1. public class Solution {
    3.      * @param S, T: Two string.
    4.      * @return: Count the number of distinct subsequences
    5.      */
    6.     public int numDistinct(String S, String T) {
    7.         if (S == null || T == null) return 0;
    8.         if (S.length() < T.length()) return 0;
    9.         if (T.length() == 0) return 1;
    12.         for (int i = 0; i < S.length(); i++) {
    13.             for (int j = T.length() - 1; j >= 0; j--) {
    14.                 if (S.charAt(i) == T.charAt(j)) {
    15.                         f[j + 1] += f[j];
    16.                 }
    17.             }
    18.         }
    20.         return f[T.length()];
    22. }
    1. 什麼是動態規劃？動態規劃的意義是什麼？ - 知乎 - 熊大大和王勐的回答值得細看，適合作爲動態規劃的科普和入門。維基百科上對動態規劃的描述感覺太過學術。
    2. - Topcoder上的一篇譯作。