什麼是動態規劃

動態規劃是一種演演算法思想或程式設計技巧，用於解決一類最佳化問題。該演演算法將複雜的問題劃分成一個個簡單的子問題，將子問題的解決方法儲存下來，以便最終得到整個問題的最優解。它適用於求解許多優化問題，如最長公共子序列、揹包問題、最短路徑等。動態規劃的核心思想是：將問題分解成一些相對簡單的子問題，並記錄每個子問題的解，同時利用子問題的解構造更大規模問題的解。

揹包問題【經典】

給定一個揹包，其最大容量為C，還有一些物品，每個物品都有自己的重量w和價值v，求在不超過揹包容量的情況下，能夠裝入的物品的最大價值。

建立一個二維陣列dp，其中dp[i][j]表示前i個物品，在揹包容量為j的情況下所能獲得的最大價值。
初始化dp陣列，即dp[0][j]和dp[i][0]都為0，因為在不放入物品或者揹包容量為0的情況下，所能獲得的最大價值為0。
對於每個物品i，從1到n進行遍歷，對於每個揹包容量j，從1到C進行遍歷。如果當前物品i的重量wi大於揹包容量j，則不能放入揹包，dp[i][j]的值與dp[i-1][j]相同；如果當前物品i的重量wi小於等於揹包容量j，則可以選擇放入物品i或者不放入物品i，選取這兩種情況能夠獲得的最大價值並賦值給dp[i][j]。
最終dp[n][C]即為所求的最大價值。

for i = 1 to n:
for j = 1 to C:
if wi > j:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi]+vi)


return dp[n][C]

最長上升子序列問題

給定一個無序的整數序列，求出它的最長上升子序列的長度。

定義狀態：設dp[i]表示以第i個元素為結尾的最長上升子序列的長度。
初始化狀態：dp[i]的初始值應設為1，因為每個元素本身都可以組成一個長度為1的上升子序列。
狀態轉移方程：對於第i個元素，如果前面存在比它小的元素j，則dp[i]可以在dp[j]的基礎上+1得到；否則dp[i]的值仍為1。轉移方程為：dp[i] = max{dp[j]+1}, 0<=j<i且nums[i] > nums[j]。
最終狀態：最終狀態為所有dp[i]中的最大值max_len。
輸出結果：返回max_len即可。

initialize dp[] with value 1
for i from 1 to n:
    for j from 0 to i-1:
        if nums[i] > nums[j]:
            dp[i] = max(dp[i], dp[j]+1)
max_len = max(dp[0...n-1])
return max_len

最大子序和問題

給定一個整數序列，從中找到一個子序列，使得該子序列中的元素之和最大。

確定狀態：因為子序列的長度不確定，所以狀態可以由子序列的結尾元素來描述。假設以第i個元素結尾的子序列的最大和為f(i)，則要求的最終結果為max{f(i)}
確定狀態轉移方程：對於以第i個元素結尾的子序列，有兩種情況：
- 包含第i個元素：f(i) = max{f(i-1)+a[i], a[i]}
- 不包含第i個元素：f(i) = 0 令maxS為當前已經搜尋到位置i時最大的子序列和，則有maxS=max{maxS, f(i)}
確定初始值：初始值需滿足轉移方程的要求，可以令f(0)=0
確定計算順序：計算順序為從左到右，即從小到大

maxSubArray(A):
n = A.length
// 初始化
f[0] = 0
maxS = A[0]
// 狀態轉移
for i from 1 to n:
f[i] = max(f[i-1] + A[i], A[i])
// 更新全域性最優解
maxS = max(maxS, f[i])
return maxS

矩陣鏈乘法問題

給定n個矩陣{A1, A2, …, An}，其中Ai的規模為pi-1 x pi（i=1,2,…,n），求完全括號化矩陣乘積A1A2…An的最小計算次數。

狀態表示：定義動態規劃狀態dp[i][j]表示從第i個矩陣乘到第j個矩陣所需的最小計算次數。
狀態轉移方程：對於i<= k < j，其中k代表第一個矩陣乘的序號，可以得到狀態轉移方程：dp[i][j] = min{dp[i][k] + dp[k+1][j] + pi-1 pk pj}。
初始狀態：對於只有一個矩陣的情況，最小計算次數為0，即dp[i][i] = 0。
計算順序：按照矩陣乘法的順序計算dp[i][j]，需要先計算dp[i][i+1]、dp[i][i+2]、dp[i][i+3]等子問題，再計算dp[i][i+2]、dp[i][i+3]、dp[i][i+4]等子問題，以此類推。
最終結果：所求的結果為dp[1][n]。

function matrixChainOrder(p):
n = length(p) - 1  // 矩陣個數
let dp[1..n, 1..n] be a new table
for i = 1 to n:
dp[i][i] = 0  // 初始化對角線元素為0
for L = 2 to n:  // L為子問題矩陣乘法長度
for i = 1 to n-L+1:
j = i + L - 1
dp[i][j] = +∞  // 初始化為正無窮
for k = i to j-1:
q = dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]
if q < dp[i][j]:
dp[i][j] = q
return dp[1][n]

最小編輯距離問題

給定兩個字串A和B，求出將A轉換成B所需的最小編輯次數（一次編輯包括插入、刪除、替換操作）。

確定狀態：定義dp[i][j]表示將A的前i個字元轉換成B的前j個字元所需的最小編輯次數。
初始化：dp[i][0] = i，表示將A的前i個字元轉換成空字串所需的編輯次數；dp[0][j] = j，表示將空字串轉換成B的前j個字元所需的編輯次數。
狀態轉移方程：若A[i] == B[j]，dp[i][j] = dp[i-1][j-1]；否則，需要考慮以下三種情況：
- 插入操作：dp[i][j] = dp[i][j-1] + 1；
- 刪除操作：dp[i][j] = dp[i-1][j] + 1；
- 替換操作：dp[i][j] = dp[i-1][j-1] + 1；取三種情況中的最小值。
返回結果：最終結果為dp[len(A)][len(B)]，其中len(A)表示字串A的長度，len(B)表示字串B的長度。

function minEditDistance(strA, strB) {
let lenA = length(strA), lenB = length(strB);
let dp[lenA+1][lenB+1];
for (let i = 0; i <= lenA; i++) {
dp[i][0] = i;
}
for (let j = 0; j <= lenB; j++) {
dp[0][j] = j;
}
for (let i = 1; i <= lenA; i++) {
for (let j = 1; j <= lenB; j++) {
if (strA[i-1] == strB[j-1]) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1;
}
}
}
return dp[lenA][lenB];
}

最長公共子序列問題

給定兩個字串S和T，求它們的最長公共子序列。

確定狀態：dp[i][j]表示S的前i個字元和T的前j個字元的最長公共子序列長度。
初始化狀態：dp[i][0]=0 且 dp [0][j]=0。
狀態轉移方程：如果S[i]=T[j]，則dp[i][j]=dp[i-1][j-1]+1；如果S[i]!=T[j]，則dp[i][j]=max(dp[i-1][j], dp[i][j-1])。
計算順序：從左往右、從上往下。
返回結果：dp[S.length()][T.length()]。

function longestCommonSubsequence(S, T) {
let dp = new Array(S.length + 1).fill(0).map(() => new Array(T.length + 1).fill(0));


for(let i = 1; i <= S.length; i++) {
    for(let j = 1; j <= T.length; j++) {
        if(S[i - 1] == T[j - 1]) {
            dp[i][j] = dp[i - 1][j - 1] + 1;
        } else {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
}

return dp[S.length][T.length];

}

樹形DP問題

給定一棵有根樹，每個節點有權值和價值，路徑上的權值為所有節點權值之和，路徑的價值為所有節點價值之和。找到根節點到所有其他節點的最大價值路徑。

定義狀態：設f[i]為以節點i為路徑終點的最大價值路徑，則所求即為所有f[i]的最大值。
狀態轉移方程：對於節點i的每個子節點j，f[i]的值為f[j]+子樹i中除j以外的所有節點到i的路徑上的價值之和。
初始狀態：任選一個節點作為根節點，根據狀態轉移方程進行DFS，求得子樹內每個節點的最大路徑價值，然後遞迴求得所有子樹的最大值。
最終結果：所有f[i]的最大值即為所求。

function dfs(node):
f[node] = value[node]
for child in children[node]:
dfs(child)
f[node] = max(f[node], f[child] + value[node] - value[child])
return f[node]


result = dfs(root)

硬幣找零問題

給定面額為d1，d2，...，dn（均為正整數）的硬幣，以及一個總金額amount（不小於1），編寫一個函數來計算可以湊成總金額所需的最少的硬幣個數。如果無解，則返回-1。

狀態表示：設dp[i]為湊成金額i所需的最少硬幣個數。
初始狀態：為了湊成金額i，最壞的情況是每次只能用面額為1的硬幣，因此dp[i]的初始值為i。
狀態轉移方程：對於每個硬幣面額j，如果可以湊成金額i，則有dp[i]=min(dp[i],dp[i-j]+1)。其中dp[i-j]表示湊成金額i-j所需的最少硬幣數，加1是因為要使用硬幣面額為j的這一枚硬幣。
最終結果：如果dp[amount]的值沒有被更新，則無解，返回-1；否則，返回dp[amount]的值。

function coinChange(coins, amount)
dp[0] = 0  // 初始狀態
for i in 1 to amount
dp[i] = amount + 1 // 初始值為i，因為最壞情況是每次只能用面額為1的硬幣
for j in coins
if i >= j
dp[i] = min(dp[i], dp[i - j] + 1) // 轉移方程
if dp[amount] > amount
return -1  // 無解
else
return dp[amount]  // 返回最少硬幣數

【技術積累】演演算法中的動態規劃【一】