我要评论1.问题描述
2.问题分析
在给定两个字符串a和b，我们需要通过在字符串a中插入空格来使得a和b的长度相同，并且使得它们的“扩展距离”最小。扩展距离是指在相同位置上字符ascii码差的绝对值之和，空格字符与其他字符的距离为k。我们需要利用动态规划算法将这个复杂问题分解成更小的子问题，自底向上的计算各个子问题并利用每次计算的结果，避免重复运算。对于这个问题我们可以定义一个二维数组dp[i][j]，其中dp[i][j]表示字符串a的前i个字符和字符串 b的前j个字符的最小扩展距离。
3.解题思路
1.初始化动态规划数组，dp[0][0] 显然为 0，因为两个空字符串的扩展距离为 0。
2.对于 dp[i][0]，即字符串 b 为空的情况，字符串 a 的扩展距离就是将 a 中的每个字符都与空格进行比较的距离之和。
3.对于 dp[0][j]，即字符串 a 为空的情况，字符串 b 的扩展距离就是将 b 中的每个字符都与空格进行比较的距离之和。
4.对于其他情况，我们需要考虑三种情况： 字符 a[i] 与字符 b[j] 匹配，那么 dp[i][j] = dp[i-1][j-1] + dist(a[i], b[j])。 字符 a[i] 与空格匹配，那么 dp[i][j] = dp[i-1][j] + k。 字符 b[j] 与空格匹配，那么 dp[i][j] = dp[i][j-1] + k。
5.我们需要取上述三种情况的最小值作为 dp[i][j] 的值，即dp[i][j]=min{ dp[i-1][j] + k + k，dp[i][j-1] + k，dp[i-1][j-1] + dist(a[i], b[j])}
6.最后，dp[len(a)][len(b)] 就是我们要找的答案。题中字符串a的长度为3，b为4。
4.算法原理
初始化第一行和第一列
dp[0][0] = 0 (两个空字符串的扩展距离为 0)
dp[1][0] = 2 (a的第一个字符 'c' 与空格的距离)
dp[2][0] = 4 (a的前两个字符 "cm" 与空格的距离)
dp[3][0] = 6 (a的前三个字符 "cmc" 与空格的距离)
dp[0][1] = 2 (b的第一个字符 's' 与空格的距离)
dp[0][2] = 4 (b的前两个字符 "sn" 与空格的距离)
dp[0][3] = 6 (b的前三个字符 "snm" 与空格的距离)
dp[0][4] = 8 (b的前四个字符 "snmn" 与空格的距离
dp值递推计算公式
dp[i][j]=min{dp[i-1][j] + k + k，dp[i][j-1] + k，
dp[i-1][j-1] + dist(a[i], b[j])}
dp值计算示例
dp[1][1] = min(dp[0][0] + |'c' - 's'|, dp[1][0] + k, dp[0][1] + k)
= min(0 + 8, 2 + 2, 2 + 2)
= min(8, 4, 4) 、
= 4
以此类推dp[3][4] = 10（最终，cmc与snmn的最小扩展距离为10）
5.代码实现
完整代码
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
int calculatedistance(char a, char b, int k) {
if (a == ' ' || b == ' ') return k;
return abs(a - b);
}
int main() {
ifstream fin("c:\\users\\xiaofanzi\\desktop\\suanfawork\\input.txt");
ofstream fout("c:\\users\\xiaofanzi\\desktop\\suanfawork\\output.txt");
string a, b;
int k;
fin >> a >> b >> k;
int m = a.length(), n = b.length();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// 初始化
for (int i = 1; i <= m; ++i) dp[i][0] = i * k;
for (int j = 1; j <= n; ++j) dp[0][j] = j * k;
// 动态规划填表
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
int cost = calculatedistance(a[i - 1], b[j - 1], k);
dp[i][j] = min({ dp[i - 1][j - 1] + cost, dp[i][j - 1] + k, dp[i - 1][j] + k });
}
}
// 打印dp表
for (int i = 0; i <= m; ++i) {
for (int j = 0; j <= n; ++j) {
cout << dp[i][j] << " ";
}
cout << endl;
}
fout << dp[m][n] << endl;
fin.close();
fout.close();
return 0;结果展示
发表评论