动态规划dp¶

一、动态规划入门¶

1、dp概述¶

递推算法：后面问题的解可以由前面问题的解递推而来。

动态规划：把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决。通常用于求解具有某种最优性质的问题。在这类问题中，可能会有多可行解，我们希望找到具有最优解。

基本思路：用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。

动态规划必须满足最优化原理与无后效性。

最优化原理：一个最优策略的子策略，也是最优的。
无后效性：如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各个状态的影响。

2、错排公式¶

设\(n\)封信，所有信都装错的情况为\(F_n\)。

当添加第\(n\)封信的时候，我们可以直接想到，这封信与前\(n-1\)封信中的一封放错，那么我们就有\(n-1\)种选择。所以我们就可以得到\((n-1) * F_{n-1}\)种情况。

如果有一封信放在正确的位置，那么第\(n\)封信与他错排，依然是一种方案。这个时候就相当于\(n-2\)封信相互错排，前\(n-1\)封中的一封信和第\(n\)封信错排。所以我们就可以得到\((n-1) * F_{n-2}\)的方案数。

到这里，我们已经可以得出这个递推式了：\(Fn = (n-1)(F_{n-1}+F_{n-2})\)

我们再想一下，代码的边界值。在只有一封信的时候，不可能装错，那么\(F_1=0\)；有两封信的时候，装错的方案数为\(F_2=1\)。

/**
 * 错排公式
 * @author  王铭颢
 * @Date  2022/11/24 00:17
 */

#include "iostream"

typedef long long ll;
using namespace std;

int main() {
    int n;
    cin >> n;
    ll a = 0, b = 1, c = 1;
    for (int i = 3; i < n; ++i) {
        c = (a + b) * (i - 1);
        a = b;
        b = c;
    }
    c = n == 1 ? 0 : c;
    cout << c << endl;
    return 0;
}

3、马踏过河卒¶

卒只能向下或者向右走，那么想要到达棋盘上的一个点，有两种方式：从左边的格子过来，或者从上边的格子过来。

所以，过河卒到达某点的路径数目等于到达与其相邻的左边点和上边点的路径数目和。

/**
 * 二维dp马踏过河卒
 * @author  王铭颢
 * @Date  2022/11/24 00:25
 */

#include "iostream"

using namespace std;
int dir[8][2] = {
        {2,  1},
        {1,  2},
        {-1, 2},
        {2,  -1},
        {-2, -1},
        {-1, -2},
        {1,  -2},
        {-2, 1}
};
int n, m, x, y;
int mp[25][25];
int dp[25][25];

int main() {
    cin >> n >> m >> x >> y;
    mp[x][y] = 1;
    for (int i = 0; i < 8; ++i) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if (tx >= 0 && ty >= 0 && tx <= n && ty <= m) {
            mp[tx][ty] = 1;
        }
    }

    dp[0][0] = 1;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (mp[i][j]) continue;
            if (i) dp[i][j] += dp[i - 1][j];
            if (j) dp[i][j] += dp[i][j - 1];
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

4、爬楼梯¶

每次走1级或者2级，求n级楼梯共有多少中走法

/**
 * 爬楼梯
 * @author  王铭颢
 * @Date  2022/11/24 01:04
 */

#include "iostream"

using namespace std;
int dp[1005];

int main() {
    int n;
    cin >> n;
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    cout << dp[n] << endl;
    return 0;
}

5、最少的步数¶

在河上有一排n个荷叶（编号依此为1,2,3····n），第i个荷叶上有一个整数ai，现在有一只小青蛙在第1个荷叶上，荷叶上的整数表示小青蛙在该位置可以向前跳跃最多的荷叶个数。求小青蛙从第1个荷叶跳到第n个荷叶用的最少的步数。

memset(dp, 0x3f, sizeof dp);：将dp的所以值改为无穷大

memset(dp, -0x3f, sizeof dp);：将dp的所以值改为无穷小

#include "iostream"

using namespace std;
int mp[10005];
int dp[10005];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> mp[i];
    }
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 1; j <= mp[i]; ++j) {
            if (i + j > n) break;
            dp[i + j] = min(dp[i + j], dp[i] + 1);
        }
    }
    cout << dp[n - 1];
    return 0;
}

二、动态规划模型¶

1、最大子段和¶

给定一个由数宇组成的序列，其中连续的一段子序列称为一个子段，子段中的所有数之和称为子段和，这里只考虑非空子段，即至少包含一个元素的子段。

/**
 * 最大子段和
 * @author  王铭颢
 * @Date  2022/11/24 01:32
 */

#include "iostream"

using namespace std;
int num, ans;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int temp;
        cin >> temp;
        num = max(temp, num + temp);
        ans = max(num, ans);
    }
    cout << ans << endl;
    return 0;
}

2、最长上升子序列¶

在原序列取任意多项，不改变他们在原来数列的先后次序，得到的序列称为原序列的子序列（不要求连续）。

最长上升子序列，就是给定序列的的一个最长的、数值从低到高排列的子序列，最长上升子序列不一定是唯一的。

/**
 * 最长上升子序列
 * @author  王铭颢
 * @Date  2022/11/24 02:38
 */

#include "iostream"

using namespace std;
int num[10005];
int dp[10005];
int ans;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> num[i];
    }
    dp[0] = 1;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (num[j] < num[i]) {
                ans = max(ans, dp[i] = max(dp[i], dp[j] + 1));
            }
        }
    }
    cout << ans << endl;
    return 0;
}

3、最长公共子序列¶

最长公共子序列：给定两个序列S1、S2，求二者公共子序列（不要求连续）S3的最长的长度。

/**
 * 最长公共子序列
 * @author  王铭颢
 * @Date  2022/11/24 02:51
 */


#include "iostream"

using namespace std;
int dp[105][105];

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    for (int i = 1; i <= s1.length(); ++i) {
        for (int j = 1; j <= s2.length(); ++j) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    cout << dp[s1.length()][s2.length()] << endl;
    return 0;
}

4、编辑距离¶

1）要求¶

给定两个字符串S和T。对于字符串T，我们允许如下三种操作：

在任意位置添加任意字符
删除存在的任意字符
将一个任意字符修改为另一个任意字符

编辑距离：问经过多少次操作之后可以将字符串T变为字符串S

2）分析¶

令\(f(i,j)\)表示s的前\(i\)位和T的前\(j\)位对齐后的最少扣分

若S[i] = T[j]，表示当前位置是对齐的，因此答案就是\(f(i-1,j-1)\)。
若S[i] != T[j]，那么在当前位置需要修改，因此答案就是 \(f(i-1,j-1)+1\)。
S的前\(i\)位和T的前\(j-1\)位对齐之后，在当前位置需要执行一次添加操作。因此此时的答案应为\(f(i,j-1)+1\)。
S的前\(i-1\)位和T的前\(j\)位对齐之后，在当前位置需要执行一次删除操作。因此此时的答案应为\(f(i-1,j)+1\)。

3）转移公式¶

4）边界处理¶

\(f(0,j)=j\)

\(f(i,0)=i\)

这是因为对于S的前0个字符，我们只能把T中的字符全部删掉。同理，对于T中的前0 个字符，我们只能选择把T中添加上S当前长度的字符。

5）代码实现¶

/**
 * 编辑距离
 * @author  王铭颢
 * @Date  2022/11/24 11:21
 */

#include "iostream"

using namespace std;
int dp[105][105];

int main() {
    string s1, s2;
    cin >> s1 >> s2;

    // 边界处理
    for (int i = 0; i < s1.length(); ++i) {
        dp[i][0] = i;
    }
    for (int j = 0; j < s2.length(); ++j) {
        dp[0][j] = j;
    }

    // 转移公式
    for (int i = 1; i < s1.length(); ++i) {
        for (int j = 1; j < s2.length(); ++j) {
            dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j])) + 1;
        }
    }

    cout << dp[s1.length() - 1][s2.length() - 1] << endl;

    return 0;
}

5、最大子矩阵和¶

转换成一维数组，枚举上下边界

1）二维前缀和¶

/**
 * 最大子矩阵和（二维前缀和）
 * @author  王铭颢
 * @Date  2022/11/24 13:54
 */

#include "iostream"

using namespace std;
int mp[1005][1005];
int s[1005][1005];

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> mp[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + mp[i][j];

    int ans = -0x3f3f3f3f;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int l = i; l <= n; l++)
                for (int r = j; r <= m; r++)
                    ans = max(ans, s[l][r] - s[l][j - 1] - s[i - 1][r] + s[i - 1][j - 1]);
    cout << ans << endl;

    return 0;
}

2）DP¶

dp不是很好理解，前缀和已经能解决很多问题。

1、把列看成一维序列，求出第i项的最大子段和。

2、枚举行的开始与结束，找到最大的差值。迭代行，输出最大值。

/**
 * 最大子矩阵和
 * @author  王铭颢
 * @Date  2022/11/24 13:54
 */

#include "iostream"

using namespace std;
int mp[1005][1005];
int sum[1005][1005];
int ans = -0x3f;

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> mp[i][j];
            ans = max(ans, mp[i][j]);
        }
    }

    if (ans <= 0) {
        cout << ans << endl;
    } else {
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                sum[i][j] = sum[i - 1][j] + mp[i][j];
            }
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                int s = 0;
                for (int k = 1; k < m; k++) {
                    if (s + sum[j][k] - sum[i - 1][k] < 0) {
                        s = 0;
                    } else {
                        s += sum[j][k] - sum[i - 1][k];
                    }
                    ans = max(ans, s);
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

6、添加成回文串¶

通过添加字符把一个非回文字符串变成回文串。

对于一个给定的字符串，最少需要添加几个字符，才能变成回文串。

字符串长度减去字符串与相反的字符串的最大公共子序列

三、背包问题¶

1、背包问题概述¶

给定一组物品，每种物品都有自己的重量和价值，现有一个背包，能承受的重量有限，在受限制的重量下，取若干物品，使得总价值最大。这一类问题，被称为背包问题。

2、01背包问题¶

每次遍历到的第i个物品，根据 w[i]和 v[i]来确定是否需要将该物品放入背包中。

对于给定的n个物品，设 v[i]、w[i]分别为第i个物品的价值和重量，C为背包的容量。

令 dp[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值。

dp[i][0]=dp[0][j]=0; 表示填入表第一行和第一列是 0
w[i]> j ：dp[i][j]=dp[i-1][j] 当准备加入新增的商品的容量大于当前背包的容量时，就直接使用上一个格的装入策略
j >= w[i]：dp[i][j]=max(v[i-1][j], dp[i]+dp[i-1][j-w[i]])当准备加入的新增的商品的容量小于等于当前背包的容量,
装入的方式
1. v[i-1][j]：就是上一个单元格的装入的最大值
2. v[i]：表示当前商品的价值
3. v[i-1][j-w[i]]：装入 i-1 商品，到剩余空间 j-w[i]的最大值
4. j>=w[i]： v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]};

/**
 * 01 背包问题
 * @author  王铭颢
 * @Date  2022/11/24 18:16
 */

#include "iostream"

using namespace std;
int goodsSize[105];
int goodsValue[105];
int dp[105][105];

int main() {
    int size, type;
    cin >> size >> type;
    for (int i = 1; i <= type; i++) {
        cin >> goodsSize[i] >> goodsValue[i];
    }

    for (int i = 1; i <= size; i++) {
        for (int j = 1; j <= type; j++) {
            if (goodsSize[i] == i) {
                // 放一个正好放满 --> 放 "这个" or "上一个品种" 中价值更高的
                dp[i][j] = max(goodsValue[i], dp[i][j - 1]);
            } else if (goodsSize[i] > i) {
                // 这个放不下 --> 放 "上一品种的"
                dp[i][j] = dp[i][j - 1];
            } else {
                // 放完还有空余 -> 放 "这个+剩下找本行相应的" or "上一个品种" 中价值更高的
                dp[i][j] = max(goodsValue[i] + dp[i - goodsSize[j]][j], dp[i][j - 1]);
            }
        }
    }
    cout << dp[size][type] << endl;
    return 0;
}

3、多重背包¶

把物品逐个拆分，则得到n个物品。原问题转化为01背包求解。

也可以在转移的过程中枚举k，代表第i个物品选取的数量，和01背包的思想一样，有如下转移

\(dp[i][v]=max(dp[i][v],dp[i-1][v-k*c_i]+k*w_i)\)