算法设计与分析-第三章

0/1 背包

走砖路

编辑距离

0/1 背包

题目大意

给定 n种物品，每种物品都有对应的重量 w[i]和价值 v[i]，同时有一个容量为 m的背包。要求从这些物品中选择装入背包的物品，使得装入背包的物品总价值最大，并且每种物品只能选择一次，不能将物品分割装入背包。

背包问题中涉及数组下标，请注意数据范围对其的影响

解法描述

算法思想

动态规划的核心思想是把原问题分解为相互重叠的子问题，通过求解子问题并保存子问题的解，来避免重复计算，从而得到原问题的最优解。对于 0/1 背包问题，定义状态 dp[i][j]表示前 i个物品放入容量为 j的背包中所能获得的最大价值。状态转移方程为：

\[ dp[i][j] = \begin{cases} dp[i - 1][j] & \text{if } j < w[i] \\ \max(dp[i - 1][j], dp[i - 1]j - w[i]] + v[i]) & \text{if } j \geq w[i] \end{cases} \]

即当背包容量 j小于当前物品重量 w[i]时，无法装入该物品，最大价值等于前 i - 1个物品放入容量为 j的背包的价值；当背包容量 j大于等于当前物品重量 w[i]时，比较不装入当前物品（价值为 dp[i - 1][j]）和装入当前物品（价值为 dp[i - 1][j - w[i]] + v[i]）的价值，取较大值作为 dp[i][j]的值 。最终 dp[n][m]就是问题的最优解。

实现方式

1. 朴素实现

   在代码中，先读取物品数量 n、背包容量 m以及每个物品的重量 w[i]和价值 v[i]。初始化一个二维数组 dp[n + 1][m + 1]，并将其值初始化为 0。然后通过两层嵌套循环，外层循环遍历物品（从 1 到 n），内层循环遍历背包容量（从 0 到 m）。在内层循环中，根据上述状态转移方程更新 dp[i][j]的值。最后输出 dp[n][m]，即能装入背包的物品的最大总价值。

//朴素做法
 for(int i = 1;i<=n;i++)
 {
     for(int j = 0;j<=m;j++)
     {
         dp[i][j] = dp[i-1][j];
         if(j>=v[i]) dp[i][j] = max(dp[i-1][j-v[i]]+w[i],dp[i][j]);//当可以放下时，检测是否值得
     }
 }
 cout<<dp[n][m];

2. 优化实现（滚动数组压缩）

   观察状态转移方程可以发现，dp[i][j]的值只与 dp[i - 1][j]和 dp[i - 1][j - w[i]]有关，即只与上一层的状态有关。因此，可以使用滚动数组将二维数组优化为一维数组。代码中定义一个一维数组 dp[m + 1]，并初始化为 0。通过两层循环，外层循环遍历物品（从 1 到 n），内层循环从背包容量 m反向遍历到当前物品重量 v[i]（因为正向遍历会导致同一个物品被多次计算）。在内层循环中，根据状态转移方程 dp[j] = max(dp[j], dp[j - v[i]] + w[i])更新 dp[j]的值。最后输出 dp[m]，得到最大总价值。

//反向遍历，滚动数组压缩
for (int i = 1; i <= n; i++) {
    for (int j = m; j >= v[i]; j--) {
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }
}
cout << dp[m];

复杂度分析

1. 时间复杂度：无论是朴素实现还是优化实现，都存在两层嵌套循环，外层循环遍历物品数量 n次，内层循环遍历背包容量 m次。所以时间复杂度均为\(O(nm)\)，其中 n是物品的数量，m是背包的容量。
2. 空间复杂度：朴素实现中，使用了一个大小为\((n + 1) \times (m + 1)\)的二维数组 dp来保存中间状态，因此空间复杂度为\(O(nm)\)。在优化实现（滚动数组压缩）中，使用了一个大小为 m + 1的一维数组 dp，空间复杂度优化为\(O(m)\)。

走砖路

题目大意

有一条小路包含 n块砖，初始位置在第一块砖，每次只能向前走一块砖或两块砖，需要求解恰好到达最后一块砖的不同走法数量。并且计算结果需要对给定的数 m取模。

解法描述

算法思想

动态规划的核心在于将复杂问题分解为相互关联的子问题，并通过保存子问题的解来避免重复计算。对于走砖路问题，定义状态 dp[i]表示到达第 i块砖的方法数。因为每次可以走一步（从 i - 1块砖走到 i块砖）或者走两步（从 i - 2块砖走到 i块砖），所以到达第 i块砖的走法数量就是到达 i - 1块砖的走法数量与到达 i - 2块砖的走法数量之和，即状态转移方程为 dp[i] = dp[i - 1] + dp[i - 2]。考虑到计算过程中数值可能过大，所以每次计算结果都对 m取模。通过逐步计算每个位置的走法数量，最终 dp[n]就是到达最后一块砖的不同走法数量（需再对 m取模）。

实现方式

1. 初始化

   在代码中，首先定义了一个常量数组 dp用于存储到达每块砖的走法数量，其大小为 N，还定义了取模值 M。读取输入的砖块数量 n。然后初始化 dp数组的前三项，dp[1] = 0（因为从起点（第 1 块砖）出发到达第 1 块砖只有 0 种额外走法），dp[2] = 1（从第 1 块砖走到第 2 块砖只有 1 种走法，即走一步），dp[3] = 2（从第 1 块砖走到第 3 块砖可以走一步到第 2 块砖再走一步，或者直接走两步，共 2 种走法）。

2. 状态转移计算

   使用一个循环从 i = 4到 i = n，根据状态转移方程 dp[i] = (dp[i - 1] + dp[i - 2]) % M计算到达每一块砖的走法数量，并对结果取模。

#include <bits/stdc++.h>
using namespace std;
const int N = 1000000, M = 100007;
int dp[N];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= 3; i++) dp[i] = i - 1;
    for (int i = 4; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % M;
    }
    cout << dp[n] % M;
    return 0;
}

复杂度分析

1. 时间复杂度：算法中存在一个从 4到 n的循环，循环次数为 n - 3次，每次循环内执行的操作时间复杂度为常数级。所以整体时间复杂度为\(O(n)\)，其中 n是砖块的数量。

2. 空间复杂度：算法使用了一个长度为 N（这里 N被定义为 1000000 ）的数组 dp来存储到达每块砖的走法数量，所以空间复杂度为\(O(n)\)，其中 n是砖块的数量。如果对空间复杂度进行优化，可以使用滚动数组，将空间复杂度降低到\(O(1)\)，因为每次计算 dp[i]只用到 dp[i - 1]和 dp[i - 2]，只需要保存这两个状态即可。

编辑距离

题目大意

计算两个由小写字母 a - z 组成的字符串之间的编辑距离。编辑距离的定义为：将一个字符串转化成另一个字符串最少需要进行的字符增加、删除、修改操作的次数。输入是一行，包含两个以空格分隔的字符串，输出是这两个字符串的编辑距离。

解法描述

算法思想

动态规划的核心在于将原问题分解为一系列相互关联的子问题，并且保存这些子问题的解，避免重复计算。对于编辑距离问题，我们定义一个二维数组 dp，其中 dp[i][j] 表示字符串 s1 的前 i 个字符和字符串 s2 的前 j 个字符之间的编辑距离。通过求解一系列子问题，最终得到原问题的解。

实现方式

1. 输入处理

• 使用 cin >> s1 + 1 >> s2 + 1 读取两个字符串，这里 s1 + 1 和 s2 + 1 是为了让字符串从下标 1 开始存储，方便后续处理。
• 通过循环计算两个字符串的长度 n1 和 n2。

2. 初始化：使用 memset(dp, 0x3f3f3f3f, sizeof dp) 将 dp 数组初始化为一个较大的值（近似无穷大），表示初始状态下还未找到有效的编辑距离。

• 初始化边界条件：
  • 当 s2 为空字符串时，将 s1 的前 i 个字符转换为 s2 （空字符串）需要删除 i 个字符，所以 dp[i][0] = i，其中 i 从 0 到 n1 - 1。
  • 当 s1 为空字符串时，将 s1 转换为 s2 的前 i 个字符需要添加 i 个字符，所以 dp[0][i] = i，其中 i 从 0 到 n2 - 1。

3. 状态转移：设字符串 s1 的长度为 n1，字符串 s2 的长度为 n2，对于 1 ≤ i ≤ n1 和 1 ≤ j ≤ n2，状态转移分为以下两种情况：

• 当 s1[i] == s2[j] 时，当前字符不需要进行修改操作。此时 dp[i][j] 可以从以下三种情况转移而来：

  • 情况一：不进行任何操作，直接继承 s1 的前 i - 1 个字符和 s2 的前 j - 1 个字符的编辑距离，即 dp[i - 1][j - 1]。
  • 情况二：删除 s1 的第 i 个字符，那么编辑距离为 dp[i - 1][j] + 1。
  • 情况三：添加 s2 的第 j 个字符到 s1 中，编辑距离为 dp[i][j - 1] + 1。

  我们取这三种情况的最小值作为 dp[i][j] 的值，用公式表示为： \[ dp[i][j] = \min\left\{dp[i - 1][j - 1], dp[i - 1][j] + 1, dp[i][j - 1] + 1\right\} \]

• 当 s1[i] != s2[j] 时，需要进行一次修改操作。同样，dp[i][j] 也可以从以下三种情况转移而来：

  • 情况一：将 s1 的第 i 个字符修改为 s2 的第 j 个字符，编辑距离为 dp[i - 1][j - 1] + 1。
  • 情况二：删除 s1 的第 i 个字符，编辑距离为 dp[i - 1][j] + 1。
  • 情况三：添加 s2 的第 j 个字符到 s1 中，编辑距离为 dp[i][j - 1] + 1。

  我们取这三种情况的最小值作为 dp[i][j] 的值，用公式表示为： \[ dp[i][j] = \min\left\{dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1, dp[i][j - 1] + 1\right\} \]

复杂度分析

• 时间复杂度：代码中有两层嵌套循环，外层循环遍历 s1 的长度 n1，内层循环遍历 s2 的长度 n2，因此时间复杂度为 \(O(n1 * n2)\)。
• 空间复杂度：使用了一个二维数组 dp 来保存子问题的解，数组大小为 N * N，因此空间复杂度为 \(O(N^2)\)，在本题中 N 为最大字符串长度。

#include <bits/stdc++.h>
using namespace std;
const int N  = 1e3 + 9;
char s1[N], s2[N];
int dp[N][N];
int main() {
    cin >> s1 + 1 >> s2 + 1;
    int n1 = 1;
    while (s1[n1] != '\0') n1++;
    int n2 = 1;
    while (s2[n2] != '\0') n2++;
    //	cout << n1 << " " << n2 << endl;
    memset(dp, 0x3f3f3f3f, sizeof dp);
    for (int i = 0; i < n1; i++) {
        dp[i][0] = i;
    }
    for (int i = 0; i < n2; i++) {
        dp[0][i] = i;
    }
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            if (s1[i] == s2[j]) {
                int tmp = dp[i - 1][j - 1];
                tmp = min(dp[i - 1][j] + 1, tmp);
                tmp = min(dp[i][j - 1] + 1, tmp);
                dp[i][j] = min(tmp, dp[i][j]);
            } else {
                int tmp = dp[i - 1][j - 1] + 1;
                tmp = min(dp[i - 1][j] + 1, tmp);
                tmp = min(dp[i][j - 1] + 1, tmp);
                dp[i][j] = min(tmp, dp[i][j]);
            }
            //			for (int x = 0; x < n1; x++) {
            //				for (int y = 0; y < n2; y++) {
            //					cout << dp[x][y] << " ";
            //				}
            //				puts("");
            //			}
            //			puts("");
        }
    }

    cout << dp[n1][n2];
    return 0;
}