【技术积累】算法中的动态规划【一】

什么是动态规划

动态规划是一种算法思想或编程技巧，用于解决一类最优化问题。该算法将复杂的问题划分成一个个简单的子问题，将子问题的解决方法保存下来，以便最终得到整个问题的最优解。它适用于求解许多优化问题，如最长公共子序列、背包问题、最短路径等。动态规划的核心思想是：将问题分解成一些相对简单的子问题，并记录每个子问题的解，同时利用子问题的解构造更大规模问题的解。

背包问题【经典】

给定一个背包，其最大容量为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]  // 返回最少硬币数