經過了前五天大量動態規劃的洗滌之後，大家有沒有覺得對填表更加熟悉了呢？在解決動態規劃的問題時，最重要的是定義一個適當的表格（也就是確定問題與子問題的格式）然後，找出問題與子問題之間的關聯！通常我們會把子問題的輸入參數稱之為狀態(State)，並且把從子問題湊合得出原問題答案的過程稱之為狀態轉移(Transition)。
狀態這個詞，通常表示的是一個系統中，可調整參數的現狀。套用到演算法解題的時候，可以解釋成當前問題的輸入值。比方說，在 LCS 問題裡面，我們定義 LCS(i, j) 代表第一個字串的第 i 前綴、與第二個字串的第 j 前綴，的最長共同部份子序列的長度——在這個定義下每一個不同的 (i, j) 取值就是一個狀態。而爬樓梯問題的階數 n，也可作為該問題的「狀態」。
狀態轉移是描述狀態與狀態之間的關聯，其實就是遞迴關係啦！狀態轉移和遞迴關係兩者基本上是一樣的東西。狀態轉移被定義出來以後，我們就會有很明確的 DP 方向可以依循，比方說計算 LCS(i, j) 會依賴 LCS(i-1, j)、LCS(i, j-1)、LCS(i-1, j-1) 這三個狀態。又或者說，計算費氏數列的時候，F(n) 會依賴 F(n-1)、F(n-2) 這兩個狀態。
狀態轉移在實作上其實有兩種方式：拉(Pull) 和 推(Push)。
這兩種轉移方式分別有不同的適用題目，目前為止我們所見到的，幾乎都是用拉的方式算出新狀態的值。未來我們會看到一些用推的比較方便的動態規劃！
修過演算法的同學們，一定會覺得很奇怪：到目前為止只提及「動態規劃就是填表」。但事實上，要完成動態規劃，其實有兩種實作方法可以選擇：Bottom-Up (填表) 以及 Top-Down (遞迴)。這兩種方法也有不同的適用題目，我們之後會慢慢討論～
有了狀態和轉移之後，估算動態規劃演算法所需的時間複雜度，這個任務就簡單啦～
以下是最簡單的估計：
O(狀態總數 x 單個狀態轉移所需時間)
於是我們可以很輕鬆地計算出解決 LCS 演算法所花時間為 O(N^2)、因為至多有 N^2 個狀態、每次轉移只要花常數時間 O(1)。而用動態規劃方法計算費氏數列所花的時間為 O(N)、因為至多有 N 個狀態、每次轉移也是花費常數時間 O(1)。
好的，今天講了這麼多，還沒寫程式的你一定手癢了對吧！那我們再來刷個題吧！
https://leetcode.com/problems/interleaving-string/
給你三個字串 s1, s2, s3。請問我們是否能夠將 s3 拆成兩個子序列，而這兩個子序列按左至右順序接起來剛好是 s1 和 s2 呢？
要用動態規劃，就來想想什麼是狀態？我們可以觀察 s3 的最後一個字元：它可能來自 s1、也可能來自 s2。如果 s1 和 s2 的最後一個字元都等於 s3 的最後一個字元，那麼我們便需要考慮子問題 (s1[:-1], s2) 和 (s1, s2[:-1])。於是，依循這個想法，我們可以定義狀態是 (i, j)：代表了 s1 的第 i 個前綴、與 s2 的第 j 個前綴。如果這兩個字串可以湊出 s3 的前綴的話，那麼 dp(i, j) = True，否則是 False。
import numpy as np
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if len(s3) != len(s1) + len(s2):
return False
dp = np.full([len(s1) + 1, len(s2) + 1], False)
dp[0, 0] = True
for i in range(0, len(s1) + 1):
for j in range(0, len(s2) + 1):
if i > 0 and s1[i-1] == s3[i+j-1]:
dp[i, j] |= dp[i-1, j]
if j > 0 and s2[j-1] == s3[i+j-1]:
dp[i, j] |= dp[i, j-1]
return dp[len(s1), len(s2)]
定義 M = len(s1)、N = len(s2)，透過陣列宣告可知總共有 (M+1)*(N+1) 個狀態、內層迴圈只花常數時間 O(1) 進行轉移。因此時間複雜度就是 O(MN)。
這題用 dfs 做還蠻快的：
https://leetcode.com/problems/interleaving-string/discuss/31888/1ms-tiny-DFS-beats-94.57
我用 c++ 實驗得到 0ms:
vector<vector<bool>> invalid;
bool dfs(const string &s1, const string &s2, const string &s3, int i, int j) {
if (invalid[i][j])
return false;
if (i + j == s3.length())
return true;
bool valid = false;
if (i < s1.length() && s1[i] == s3[i + j])
valid = dfs(s1, s2, s3, i + 1, j);
if (!valid && j < s2.length() && s2[j] == s3[i + j])
valid = dfs(s1, s2, s3, i, j + 1);
invalid[i][j] = !valid;
return valid;
}
bool isInterleave_dfs_0ms(string s1, string s2, string s3) {
const int m = s1.length(), n = s2.length();
if (m + n != s3.length())
return false;
invalid.resize(m + 1, vector<bool>(n + 1));
return dfs(s1, s2, s3, 0, 0);
}
謝謝您提供一個使用 top-down 方法的動態規劃解決這個問題！
這個以 DFS 實作的演算法也是動態規劃的一種～因為把算過的不合法的 i, j 都記錄下來了，最壞情形下的時間複雜度雖然也是 O(MN) ，但在一般情況下不會跑滿 M*N 的所有組合，相當有效率！
啊啊，確實是動態規劃 :P
時間複雜度依然是 O(MN)！
iThome鐵人賽
看影片追技術