d p[i][j]=\min (d p[i-1][j]+\operatorname{ord}(s 1[i-1]), d p[i][j-1]+\operatorname{ord}(s 2[j-1]), d p[i-1][j-1]+\operatorname{ord}(s 1[i-1])+\operatorname{ord}(s 2[j-1]))
3. 解决方法
3.1 动态规划方法
创建一个二维数组
d p
，大小为
(m+1) \times(n+1)
，其中
m
和
n
分别是
s 1
和
s 2
的长度。
初始化边界条件：
dp[i][0]=\sum_{k=0}^{i-1} \text{ord}(s1[k])
，表示将
s 1
的前
i
个字符转换为空字符串所需删除的 ASCII 值之和。
dp[0][j]=\sum_{k=0}^{j-1} \text{ord}(s2[k])
，表示将
s 2
的前
j
个字符转换为空字符串所需删除的 ASCII 值之和。
使用双重石环填充 dp 数组，依赖于前面的状态。
最终结果为
\mathrm{dp}[\mathrm{m}][\mathrm{n}]
。
3.2 空间优化的动态规划
可以使用一维数组来优化空间复杂度，减少内存占用。
4. 进一步优化
通过空间优化，降低内存占用的同时保持时间复杂度为
O(m * n)
，适合中等规模的字符串比较。
5. 小总结
最小 ASCII 删除和问题通过动态规划有效地解决了两个字符串之间的转换成本。
该问题的解法展示了如何设计状态转移方程，并且可以通过空间优化提高性能。
理解该问题不仅有助于掌握动态规划的应用，还为处理相似问题提供了思路。
以上就是两个字符串的最小ASCII删除和问题的基本思路。
代码实现
Python
Python3代码实现
代码语言：javascript
复制
class Solution:
def minimumDeleteSum(self, s1: str, s2: str) -> int:
m, n = len(s1), len(s2)
# 创建dp数组
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 初始化边界条件
for i in range(1, m + 1):
dp[i][0] = dp[i - 1][0] + ord(s1[i - 1]) # 删除s1的字符
for j in range(1, n + 1):
dp[0][j] = dp[0][j - 1] + ord(s2[j - 1]) # 删除s2的字符
# 填充dp数组
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] # 字符相同
else:
dp[i][j] = min(dp[i - 1][j] + ord(s1[i - 1]), # 删除s1的字符
dp[i][j - 1] + ord(s2[j - 1]), # 删除s2的字符
dp[i - 1][j - 1] + ord(s1[i - 1]) + ord(s2[j - 1])) # 同时删除
# 返回最小ASCII删除和
return dp[m][n]
Python 代码解释
初始化：创建 dp 数组并设置边界条件，分别表示将 s1 和 s2 转换为空字符串的操作。
填充 dp 数组：使用双重循环计算每个子问题的最小 ASCII 删除和，依赖于之前的结果。
返回结果：最终返回 dp[m][n]，即将 s1 转换为 s2 所需的最小 ASCII 删除和。
C++
C++代码实现
代码语言：javascript
复制
class Solution {
public:
int minimumDeleteSum(string s1, string s2) {
int m = s1.size(), n = s2.size();
// 创建dp数组
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// 初始化边界条件
for (int i = 1; i <= m; i++) {
dp[i][0] = dp[i - 1][0] + s1[i - 1]; // 删除s1的字符
}
for (int j = 1; j <= n; j++) {
dp[0][j] = dp[0][j - 1] + s2[j - 1]; // 删除s2的字符
}
// 填充dp数组
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1]; // 字符相同
} else {
dp[i][j] = min({dp[i - 1][j] + s1[i - 1], // 删除s1的字符
dp[i][j - 1] + s2[j - 1], // 删除s2的字符
dp[i - 1][j - 1] + s1[i - 1] + s2[j - 1]}); // 同时删除
}
}
}
// 返回最小ASCII删除和
return dp[m][n];
}
};
粤公网安备44030502008569号