Dynamic Programming - 動態規劃
動態規劃是一種「分治」的思想,通俗一點來說就是「大事化小,小事化無」的藝術。在將大問題化解爲小問題的「分治」過程中,保存對這些小問題已經處理好的結果,並供後面處理更大規模的問題時直接使用這些結果。嗯,感覺講了和沒講一樣,還是不會使用動規的思想解題...
下面看看知乎上的熊大大對動規比較「正經」的描述。
動態規劃是通過拆分問題,定義問題狀態和狀態之間的關係,使得問題能夠以遞推(或者說分治)的方式去解決。
以上定義言簡意賅,可直接用於實戰指導,不愧是參加過NOI的。
動規的思想雖然好理解,但是要真正活用起來就需要下點功夫了。建議看看下面知乎上的回答。
動態規劃最重要的兩個要點:
- 狀態(狀態不太好找,可先從轉化方程入手分析)
- 狀態間的轉化方程(從題目的隱含條件出發尋找遞推關係)
其他的要點則是如初始化狀態的確定(由狀態和轉化方程得知),需要的結果(狀態轉移的終點)
動態規劃問題中一般從以下四個角度考慮:
- 狀態(State)
- 狀態間的轉移方程(Function)
- 狀態的初始化(Initialization)
- 返回結果(Answer)
動規適用的情形:
- 最大值/最小值
- 有無可行解
- 求方案個數(如果需要列出所有方案,則一定不是動規,因爲全部方案爲指數級別複雜度,所有方案需要列出時往往用遞歸)
- 給出的數據不可隨便調整位置
單序列(DP_Sequence)
單序列動態規劃的狀態通常定義爲:陣列前 i 個位置, 數字, 字母 或者 以第i個爲... 返回結果通常爲陣列的最後一個元素。
按照動態規劃的四要素,此類題可從以下四個角度分析。
- State: f[i] 前i個位置/數字/字母...
- Function: f[i] = f[i-1]... 找遞推關係
- Initialization: 根據題意進行必要的初始化
- Answer: f[n-1]
雙序列(DP_Two_Sequence)
一般有兩個陣列或者兩個字符串,計算其匹配關係。雙序列中常用二維陣列表示狀態轉移關係,但往往可以使用滾動陣列的方式對空間複雜度進行優化。舉個例子,以題 Distinct Subsequences 爲例,狀態轉移方程如下:
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]
的值。所以若想得到上一輪的結果,必須在內循環使用逆推的方式進行。文字表述比較模糊,可以自行畫一個二維矩陣的轉移矩陣來分析,認識到這一點非常重要。
小結一下,使用滾動陣列的核心在於:
- 狀態轉移矩陣中只能取
f[i+1][*]
和f[i][*]
, 這是使用滾動陣列的前提。 - 外循環使用 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
- 什麼是動態規劃?動態規劃的意義是什麼? - 知乎 - 熊大大和王勐的回答值得細看,適合作爲動態規劃的科普和入門。維基百科上對動態規劃的描述感覺太過學術。
- 動態規劃:從新手到專家 - Topcoder上的一篇譯作。