时间戳

首页 > 技术文章 > 算法复习——动态规划

算法复习——动态规划

VanHa0101 2020-12-26 15:59 原文

0-1背包问题、最大连续子数组问题、最长公共子序列、最长公共子串、最小编辑距离、钢条切割、矩阵链乘

0-1背包问题、最大连续子数组问题、最长公共子序列、最长公共子串、最小编辑距离、钢条切割、矩阵链乘

动态规划问题的一般步骤：

  1. 给出问题的表示，明确子问题
  2. 分析最优结构，构造递推公式
  3. 确定计算顺序，依次求解问题
  4. 记录决策过程，输出最优方案

0-1背包

动规方程：

用\(p[i,c]\)表示前i个物品在背包容量为c时能选择的最大价值。

\(dp[i,c] = max\{dp[i-1,c-v_i] + p_i, dp[i-1,c]\}\)

所以0-1背包问题就是求\(p[n,C]\)

伪代码：

//初始化
for(i=0 to C) { //前0个物品，背包容量是C时
    dp[0][i] = 0;
}
for(i=0 to n) { //前i个物品，背包容量是0时
    dp[i][0] = 0;
}
//i表示前i个物品
for(i=1 to n) {
    //j表示当前背包容量
    for(j=1 to C) {
        // 如果选择这个物品装入背包
        if ((v[i] < C) and ( dp[i-1][j-v[i]] + p[i] > dp[i-1][j])){
            dp[i][j] = dp[i-1][j-v[i]] + p[i];
        }
        // 如果背包容量装不下v[i]或者装入背包后总价值变小，那么选择不装入
        else {
            dp[i][j] = dp[i-1][j];
        }
    }
}
// 选择最优的方案
return dp[n][C];

时间复杂度：\(O(n*c)\)

总结，解决0-1背包问题的思路：

  1. 有n种物品，其对应的体积为\(v_i\)， 价值为\(p_i\)，想要求容量为C的背包，能装下物品的最大价值，用dp[i][j]表示前i种物品，在背包容量为j的情况下能装下物品的最大价值
  2. 构造递推式，子问题和原问题之间的关系，\(dp[i,c] = max\{dp[i-1,c-v_i] + p_i, dp[i-1,c]\}\)
  3. 确定计算的顺序，就是从前往后递推
  4. 记录...

最大连续子数组问题

dp[i]表示以X[i]开头的最大子数组的和，所以要从后往前计算

如果用dp[i]表示以X[i]结尾的最大子数组的和，则从前往后计算

dp[n] = X[n]
Rec[n] = n; // 用来记录选择了哪些元素
for(i=n-1 to 1) {
    //如果以X[i+1]开头的最大子数组的和dp[i+1]大于0，那么以X[i]开头的最大子数组的和dp[i]等于X[i]+ dp[i+1]
    if(dp[i+1] > 0) { 
        dp[i] = dp[i+1] + X[i];
    	Rec[i] = Rec[i+1]; //
    }
    else {
        dp[i] = X[i];
        Rec[i] = i;
    }
}
// 遍历子数组，得到最大子数组的和、选择的元素
Smax = dp[1];

for(i=2 to n) {
    if (Smax < dp[i]) {
        Smax = dp[i];
        l = i;
        r = Rec[i];
    }
}

return Smax, l , r;

时间复杂度\(O(n)\)

最长公共子序列

原始问题：X[1..n] Y[1..m]两个字符串，求其最长公共子序列

用dp[i][j]表示X[1..i], Y[1..j]的最长公共子序列长度

递推式：

\(if X[i] == Y[j]: dp[i][j] = dp[i-1][j-1] + 1;\)

\(else: dp[i][j] = max\{dp[i][j-], dp[i-1][j]\}\)

LCS(){
    // 初始化
    for(i=0 to n) {
    	dp[i][0] = 0;
    }
    for(j=0 to m) {
        dp[0][j] = 0;
    }

    rec[0..n][0..m]; // 用来记录选择的子串

    for(i=1 to n) {
        for(j=1 to m) {
            // X[i] == Y[j]
            if(X[i] == Y[j]) {
                dp[i][j] = dp[i-1][j-1] + 1; 
                rec[i][j] = 'LU'; //来自表格的左上
            }
            // X[i] != Y[j]
            else if(dp[i-1][j] >= dp[i][j-1]) {
                dp[i][j] = dp[i-1][j];
                rec[i][j] = 'U'; //来自表格的上面
            }
            else {
                dp[i][j] = dp[i][j-1];
                rec[i][j] = 'L' //来自表格的左边
            }
        }
    }

}


PrintLCS(rec[][], i, j)
{
    if(i==0 or j==0) {
        return NULL;
    }
    if(rec[i][j] == 'LU') {  // 只有这里是相等的，需要打印一个字符
        PrintLCS(rec, i-1, j-1);
        print(x[i]);
    }
    
    else if(rec[i][j] == 'L') {
        PrintLCS(rec, i, j-1);
       
    }
    
    else if(rec[i][j] == 'U') {
        PrintLCS(rec, i-1, j)
    }
}

时间复杂度\(O(n*m)\)

最长公共子串

子序列不要求连续，但是子串要求是连续的

递推式：

\(if X[i] == Y[j]: dp[i][j] = dp[i-1][j-1] + 1;\)

\(else: dp[i][j] = 0\)

伪代码：

// 初始化
for(i=1 to n) {
    dp[i][0] = 0;
}
for(j=1 to m) {
    dp[0][j] = 0;
}
//
for(i=1 to n) {
    for(j=1 to m) {
        if(X[i] == Y[j]) {
            dp[i][j] = dp[i-1][j-1] + 1; 
        }
        else {
            dp[i][j] = 0;
        }
    }
}
return dp[n][m]

时间复杂度\(O(n*m)\)

最小编辑距离

有点复杂，最后复习

下面这两个是同一种类型的，都需要遍历子问题

钢条切割

C[i]表示切割长度为i的钢条所能获得的最大收益

$C[i] = max_{1\le j\le i-1}{p[j] + C[i-j]], p[i]} $

c[0] = 0;
for(i=1 to n) {
    q = p[i]; // 不切割
    for(j=1 to i-1) { // 枚举子问题，找最大值
        if (p[j]+C[i-j] > q) {
            q = p[j] + C[i-j]
        }
    }
    C[i] = q;
}
return C[n]

时间复杂度为：\(O(n^2)\)

矩阵链乘

明确原始问题：

明确原始问题

推荐阅读