1. 動態規劃的適用場景

動態規劃常常適用于有重疊子問題和最優子結構性質的問題，動態規劃方法所耗時間往往遠少于樸素解法。

2. 動態規劃的基本思想

動態規劃背后的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再合并子問題的解以得出原問題的解。
通常許多子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，從而減少計算量：一旦某個給定子問題的解已經算出，則將其記憶化存儲，以便下次需要同一個子問題解之時直接查表。這種做法在重復子問題的數目關于輸入的規模呈指數增長時特別有用。

2.1 重疊子問題

動態規劃在查找有很多重疊子問題的情況的最優解時有效。它將問題重新組合成子問題。為了避免多次解決這些子問題，它們的結果都逐漸被計算并被保存，從簡單的問題直到整個問題都被解決。因此，動態規劃保存遞歸時的結果，因而不會在解決同樣的問題時花費時間。

2.2 最優子結構

動態規劃只能應用于有最優子結構的問題。最優子結構的意思是局部最優解能決定全局最優解（對有些問題這個要求并不能完全滿足，故有時需要引入一定的近似）。簡單地說，問題能夠分解成子問題來解決。

3. 動態規劃的三要素

• 最優子結構性質。如果問題的最優解所包含的子問題的解也是最優的，我們就稱該問題具有最優子結構性質（即滿足最優化原理）。最優子結構性質為動態規劃算法解決問題提供了重要線索。
• 無后效性。即子問題的解一旦確定，就不再改變，不受在這之后、包含它的更大的問題的求解決策影響。
• 子問題重疊性質。子問題重疊性質是指在用遞歸算法自頂向下對問題進行求解時，每次產生的子問題并不總是新問題，有些子問題會被重復計算多次。動態規劃算法正是利用了這種子問題的重疊性質，對每一個子問題只計算一次，然后將其計算結果保存在一個表格中，當再次需要計算已經計算過的子問題時，只是在表格中簡單地查看一下結果，從而獲得較高的效率。

4. 動態規劃算法的設計步驟：

1. 刻畫最優解的結構特征（尋找最優子結構）
2. 遞歸地定義最優解的值（確定狀態轉移方程）
3. 計算最優解的值（有兩種方法：帶備忘錄自頂向下法、自底向上法）
4. 利用計算出的信息構造一個最優解（通常是將具體的最優解輸出）

5. 一般的解法

把動態規劃的解法分為自頂向下和自底向上兩種方式。
自頂向下的方式其實就是使用遞歸來求解子問題，最終解只需要調用遞歸式，子問題逐步往下層遞歸的求解。我們可以使用緩存把每次求解出來的子問題緩存起來，下次調用的時候就不必再遞歸計算了。
自底向上是另一種求解動態規劃問題的方法，它不使用遞歸式，而是直接使用循環來計算所有可能的結果，往上層逐漸累加子問題的解。

注：一般看到string，往dp (dfs+memo) 上靠就對了

 

32. Longest Valid Parentheses:

dp[i]表示到i為止合法的()長度

s[i] == ')' :

dp[i] = dp[i-2] + 2                          ( s[i]=='(' )

dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]  ( s[i-1] == ')' && s[i-1-dp[i-1]] == '(' )

注意判斷數組下標值是否存在

 

72. Edit Distance

將word1轉換成word2：

三種操作：插入/刪除/替換 一個字符

dp[i][j]表示word1 [0, i)，word2 [0, j) 子串轉換成功時的最少轉換次數

初始化: dp[0][j]=j 插入操作，dp[i][0]=i 刪除操作

word1[i-1]==word2[j-1]: dp[i][j] = dp[i-1][j-1]

word1[i-1]!=word2[j-1]:  dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j])) + 1;

對應三種操作：替換 dp[i-1][j-1] + 1, 刪除(word1[i-1])  dp[i-1][j] + 1,

　　　　　　　插入(word1[i-1]后插入word2[j-1]才兩個子串相同 <=> 刪除word2[j-1]使得兩個子串相同) dp[i][j-1] + 1 

 

87. Scramble String

判斷一個字符串是否由原字符串經過scramble變換得到，變換如下：

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

判斷一個字符串是scramble有兩種情況：

把兩個字符串從中間某位置切開 

1. s1[i...i+len-1] 左邊和 s2[j...j+len-1] 左邊部分是不是 scramble，以及s1[i...i+len-1] 右邊和 s2[j...j+len-1] 右邊部分是不是 scramble；

2. s1[i...i+len-1] 左邊和 s2[j...j+len-1] 右邊部分是不是 scramble，以及s1[i...i+len-1] 右邊和 s2[j...j+len-1] 左邊部分是不是 scramble。

如果以上兩種情況有一種成立，說明 s1[i...i+len-1] 和 s2[j...j+len-1] 是 scramble。

res[i][j][len] 表示起點為s1[i]和s2[j]，長度均為len的兩個子串是否為scramble。

狀態轉移方程：res[i][j][len] = || ((res[i][j][k] && res[i+k][j+k][len-k]) || (res[i][j+len-k][k]&&res[i+k][j][len-k])) 對于所有 1<=k<len

 

96. Unique Binary Search Trees

dp[i]表示i個數時構成不同BST的個數

枚舉每個數為頂點，依次劃分為左右兩部分。

狀態轉移方程：dp[i] += (dp[j-1]*dp[i-j])  j=[1, i]

 

115. Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

dp[i][j] 表示S[0, i)包含T[0, j)子串的個數

1. General case 1: dp[i][j] = dp[i - 1][j] if t[j - 1] != s[i - 1];  s[i - 1]肯定不能在子串中
2. General case 2: dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] if t[j - 1] == s[i - 1]; 去掉當前匹配字符的s子串
3. Boundary case 1: dp[0][j] = 0 for all positive j;
4. Boundary case 2: dp[i][0] = 1 for all i. 空是任何字符串的子集

狀態轉移方程：dp[i][j] = dp[i-1][j] + ( S[i - 1] == T[j - 1] ? dp[i - 1][j - 1] : 0)

 

97. Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

dp[i][j]表示s1 [0, i), s2 [0, j)兩個字符串可以構成s3 [0, i+j)

s1當前字符與s3當前字符相同：s1[i-1] == s3[i+j-1] 則 dp[i][j] = dp[i - 1][j]

s2當前字符與s3當前字符相同:  s2[j-1] == s3[i+j-1] 則 dp[i][j] = dp[i][j - 1]

狀態轉移方程：dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i - 1 + j]) || (dp[i][j - 1] && s2[j - 1] == s3[j - 1 + i]);

 

123. Best Time to Buy and Sell Stock III

兩次股票交易，最大利潤

f[i, j] 表示到prices[0, j)為止i次交易的最大利潤

狀態轉移方程：對第j天的股票是否做賣出操作

f[i, j] = max(f[i, j-1], prices[j] - prices[k] + f[i-1, k]) { k 屬于 [0, j-1] }

        = max(f[i, j-1], prices[j] + max(f[i-1, k] - prices[k])) {利用j循環進行k循環的優化}

 

兩個雞蛋測雞蛋摔碎的臨界樓層

最重要的是要找到子問題。做如下的分析，假設f{n}表示從第n層樓扔下雞蛋，沒有摔碎的最少嘗試次數。第一個雞蛋，可能的落下位置[1, n], 第一個雞蛋從第i層扔下，有兩個情況：

• 碎了，第二個雞蛋，需要從第一層開始試驗，有i-1次機會
• 沒碎，兩個雞蛋，還有n-i層。這個就是子問題了f{n-i}

所以，當第一個雞蛋，由第i個位置落下的時候，要嘗試的次數為1 + max(i - 1, f{n - i})，那么對于每一個i，嘗試次數最少的，就是f{n}的值。狀態轉移方程如下： f{n} = min(1 + max(i - 1, f{n - 1}) ) 其中: i的范圍為(1, n), f{1} = 1 

推廣動態規劃，可以推廣為n層樓，m個雞蛋。如下分析： 假設f{n,m}表示n層樓、m個雞蛋時找到最高樓層的最少嘗試次數。當第一個雞蛋從第i層扔下，如果碎了，還剩m-1個雞蛋，為確定下面樓層中的安全樓層，還需要f{i-1,m-1}次，找到子問題；不碎的話，上面還有n-i層，還需要f[n-i,m]次，又一個子問題。 狀態轉移方程如下： f{n, m} = min(1 + max(f{n - 1, m - 1}, f{n - i, m}) ) 其中： i為(1, n), f{i, 1} = i