做义工的同城网站,v9网站模板,营销型网站建设可行性分析,搜索关键词的软件动态规划—712. 两个字符串的最小ASCII删除和 前言题目描述基本思路1. 问题定义2. 理解问题和递推关系3. 解决方法3.1 动态规划方法3.2 空间优化的动态规划 4. 进一步优化5. 小总结 代码实现PythonPython3代码实现Python 代码解释 CC代码实现C 代码解释 总结: 前言
在字符串处… 动态规划—712. 两个字符串的最小ASCII删除和 前言题目描述基本思路1. 问题定义2. 理解问题和递推关系3. 解决方法3.1 动态规划方法3.2 空间优化的动态规划 4. 进一步优化5. 小总结 代码实现PythonPython3代码实现Python 代码解释 CC代码实现C 代码解释 总结: 前言
在字符串处理的过程中如何有效地将两个字符串转换为相同的形式是一个重要的问题。最小 ASCII 删除和问题提供了一种评估字符串相似性的有效方法通过计算所需删除字符的 ASCII 值和为我们提供了清晰的转换成本。本文将探讨这一问题的基本思路并给出动态规划的实现方法最后展示 Python 和 C 的具体代码。
题目描述 基本思路
1. 问题定义
最小 ASCII 删除和问题要求我们找出将两个字符串 s 1 s 1 s1 和 s 2 s 2 s2 转换为相同字符串所需删除的字符的最小 ASCII 值之和。换句话说计算出为了使两个字符串相同所需删除的字符的 ASCII 值的总和。
2. 理解问题和递推关系
对于两个字符串 s 1 s 1 s1 和 s 2 s 2 s2 我们可以定义 dp[i][j] 为将 s 1 s 1 s1 的前 i i i 个字符和 s 2 s 2 s2 的前 j个字符变为相同的最小 ASCII 删除和。递推关系如下 如果 s 1 [ i − 1 ] s 2 [ j − 1 ] s 1[i-1]s 2[j-1] s1[i−1]s2[j−1] 那么不需要删除任何字符 d p [ i ] [ j ] d p [ i − 1 ] [ j − 1 ] d p[i][j]d p[i-1][j-1] dp[i][j]dp[i−1][j−1] 。如果 s 1 [ i − 1 ] ! s 2 [ j − 1 ] s 1[i-1]!s 2[j-1] s1[i−1]!s2[j−1], 则有三种情况: 删除 s 1 [ i − 1 ] s1[i-1] s1[i−1]代价为 ord ( s 1 [ i − 1 ] ) d p [ i − 1 ] [ j ] \operatorname{ord}(s 1[i-1])d p[i-1][j] ord(s1[i−1])dp[i−1][j] 。删除 s 2 [ j − 1 ] s 2[j-1] s2[j−1] 代价为 ord ( s 2 [ j − 1 ] ) d p [ i ] [ j − 1 ] \operatorname{ord}(s 2[j-1])d p[i][j-1] ord(s2[j−1])dp[i][j−1] 。同时删除 s 1 [ i − 1 ] s 1[i-1] s1[i−1] 和 s 2 [ j − 1 ] s 2[j-1] s2[j−1] 代价为 ord ( s 1 [ i − 1 ] ) ord ( s 2 [ j − 1 ] ) dp [ i − 1 ] [ j − \operatorname{ord}(s 1[i-1])\operatorname{ord}(s 2[j-1])\operatorname{dp}[i-1][j- ord(s1[i−1])ord(s2[j−1])dp[i−1][j− 1]. 因此综合以上情况: d p [ i ] [ j ] min ( d p [ i − 1 ] [ j ] ord ( s 1 [ i − 1 ] ) , d p [ i ] [ j − 1 ] ord ( s 2 [ j − 1 ] ) , d p [ i − 1 ] [ j − 1 ] ord ( s 1 [ i − 1 ] ) ord ( s 2 [ j − 1 ] ) ) 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])) dp[i][j]min(dp[i−1][j]ord(s1[i−1]),dp[i][j−1]ord(s2[j−1]),dp[i−1][j−1]ord(s1[i−1])ord(s2[j−1]))
3. 解决方法
3.1 动态规划方法
创建一个二维数组 d p d p dp 大小为 ( m 1 ) × ( n 1 ) (m1) \times(n1) (m1)×(n1) 其中 m m m 和 n n n 分别是 s 1 s 1 s1 和 s 2 s 2 s2 的长度。初始化边界条件 d p [ i ] [ 0 ] ∑ k 0 i − 1 ord ( s 1 [ k ] ) dp[i][0]\sum_{k0}^{i-1} \text{ord}(s1[k]) dp[i][0]∑k0i−1ord(s1[k])表示将 s 1 s 1 s1 的前 i i i 个字符转换为空字符串所需删除的 ASCII 值之和。 d p [ 0 ] [ j ] ∑ k 0 j − 1 ord ( s 2 [ k ] ) dp[0][j]\sum_{k0}^{j-1} \text{ord}(s2[k]) dp[0][j]∑k0j−1ord(s2[k])表示将 s 2 s 2 s2 的前 j j j 个字符转换为空字符串所需删除的 ASCII 值之和。 使用双重石环填充 dp 数组依赖于前面的状态。最终结果为 d p [ m ] [ n ] \mathrm{dp}[\mathrm{m}][\mathrm{n}] dp[m][n] 。
3.2 空间优化的动态规划
可以使用一维数组来优化空间复杂度减少内存占用。
4. 进一步优化
通过空间优化降低内存占用的同时保持时间复杂度为 O ( m ∗ n ) O(m * n) O(m∗n)适合中等规模的字符串比较。
5. 小总结
最小 ASCII 删除和问题通过动态规划有效地解决了两个字符串之间的转换成本。该问题的解法展示了如何设计状态转移方程并且可以通过空间优化提高性能。理解该问题不仅有助于掌握动态规划的应用还为处理相似问题提供了思路。
以上就是两个字符串的最小ASCII删除和问题的基本思路。
代码实现
Python
Python3代码实现
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代码实现
class Solution {
public:int minimumDeleteSum(string s1, string s2) {int m s1.size(), n s2.size();// 创建dp数组vectorvectorint dp(m 1, vectorint(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];}
};C 代码解释
初始化创建 dp 数组并设置边界条件分别表示将 s1 和 s2 转换为空字符串的操作。动态规划填充使用双重循环遍历每个可能的子问题依据字符是否相同来更新 dp 数组。返回结果返回 dp[m][n]即将 s1 转换为 s2 所需的最小 ASCII 删除和。 总结:
最小 ASCII 删除和问题通过动态规划有效地解决了字符串之间的转换成本具有广泛的实际应用。理解并掌握该问题的解法不仅对学习动态规划有帮助还为处理其他类似问题提供了思路。
