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

什么是动态规划

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

背包问题【经典】

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

 

热门相关:地球第一剑      梦回大明春   朕是红颜祸水   豪门重生盛世闲女