什么是動態規劃

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

背包問題【經典】

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

1. 創建一個二維陣列dp，其中dp[i][j]表示前i個物品，在背包容量為j的情況下所能獲得的最大價值，

2. 初始化dp陣列，即dp[0][j]和dp[i][0]都為0，因為在不放入物品或者背包容量為0的情況下，所能獲得的最大價值為0，

3. 對于每個物品i，從1到n進行遍歷，對于每個背包容量j，從1到C進行遍歷，如果當前物品i的重量wi大于背包容量j，則不能放入背包，dp[i][j]的值與dp[i-1][j]相同；如果當前物品i的重量wi小于等于背包容量j，則可以選擇放入物品i或者不放入物品i，選取這兩種情況能夠獲得的最大價值并賦值給dp[i][j]，

4. 最終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]

最長上升子序列問題

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

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

最大子序和問題

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

1. 確定狀態： 因為子序列的長度不確定，所以狀態可以由子序列的結尾元素來描述，假設以第i個元素結尾的子序列的最大和為f(i)，則要求的最終結果為max{f(i)}

2. 確定狀態轉移方程： 對于以第i個元素結尾的子序列，有兩種情況：

   • 包含第i個元素：f(i) = max{f(i-1)+a[i], a[i]}
   • 不包含第i個元素：f(i) = 0 令maxS為當前已經搜索到位置i時最大的子序列和，則有maxS=max{maxS, f(i)}

3. 確定初始值： 初始值需滿足轉移方程的要求，可以令f(0)=0

4. 確定計算順序： 計算順序為從左到右，即從小到大

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的最小計算次數，

1. 狀態表示：定義動態規劃狀態dp[i][j]表示從第i個矩陣乘到第j個矩陣所需的最小計算次數，

2. 狀態轉移方程：對于i<= k < j，其中k代表第一個矩陣乘的序號，可以得到狀態轉移方程：dp[i][j] = min{dp[i][k] + dp[k+1][j] + pi-1 pk pj}，

3. 初始狀態：對于只有一個矩陣的情況，最小計算次數為0，即dp[i][i] = 0，

4. 計算順序：按照矩陣乘法的順序計算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]等子問題，以此類推，

5. 最終結果：所求的結果為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所需的最小編輯次數（一次編輯包括插入、洗掉、替換操作），

1. 確定狀態：定義dp[i][j]表示將A的前i個字符轉換成B的前j個字符所需的最小編輯次數，

2. 初始化：dp[i][0] = i，表示將A的前i個字符轉換成空字串所需的編輯次數；dp[0][j] = j，表示將空字串轉換成B的前j個字符所需的編輯次數，

3. 狀態轉移方程：若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； 取三種情況中的最小值，

4. 回傳結果：最終結果為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，求它們的最長公共子序列，

1. 確定狀態：dp[i][j]表示S的前i個字符和T的前j個字符的最長公共子序列長度，
2. 初始化狀態：dp[i][0]=0 且 dp [0][j]=0，
3. 狀態轉移方程： 如果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])，
4. 計算順序：從左往右、從上往下，
5. 回傳結果：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問題

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

1. 定義狀態：設f[i]為以節點i為路徑終點的最大價值路徑，則所求即為所有f[i]的最大值，
2. 狀態轉移方程：對于節點i的每個子節點j，f[i]的值為f[j]+子樹i中除j以外的所有節點到i的路徑上的價值之和，
3. 初始狀態：任選一個節點作為根節點，根據狀態轉移方程進行DFS，求得子樹內每個節點的最大路徑價值，然后遞回求得所有子樹的最大值，
4. 最終結果：所有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，

1. 狀態表示：設dp[i]為湊成金額i所需的最少硬幣個數，
2. 初始狀態：為了湊成金額i，最壞的情況是每次只能用面額為1的硬幣，因此dp[i]的初始值為i，
3. 狀態轉移方程：對于每個硬幣面額j，如果可以湊成金額i，則有dp[i]=min(dp[i],dp[i-j]+1)，其中dp[i-j]表示湊成金額i-j所需的最少硬幣數，加1是因為要使用硬幣面額為j的這一枚硬幣，
4. 最終結果：如果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]  // 回傳最少硬幣數

標籤：其他

上一篇：10.1. Java性能調優

下一篇：返回列表