142. 两个字符串的最小 ASCII 删除总和（卡码网周赛第二十五期（23年B站笔试真题））
题目链接
142. 两个字符串的最小 ASCII 删除总和（卡码网周赛第二十五期（23年B站笔试真题））
题目描述
给定两个字符串 s1 和 s2（0 <= s1.length, s2.length <= 1000），返回使两个字符用相等所需删除字符的 ASCLL 值的最小和。
s1 和 s2 由小写英文字母组成。
输入
输入共两行，每行一个字符串。
输出
输出一个正整数，表示使两个字符用相等所需删除字符的 ASCLL 值的最小和。
样例输入
sea
eat
样例输出
231
提示
解释:在“sea”中删除“s”并将"s”的值(115)加入总和。
在"eat”中删除“t“并将116 加入总和。
结束时，两个字符串相等，115+116 =231 就是符合条件的很小和。
题解1（C++版本）
#include<bits/stdc++.h>
using namespace std;const int N = 1e3 + 10;
char s[N], t[N];int n, m, dp[N][N]; // dp[i][j]表示使s1[0,i - 1]和s2[0, j - 1]这两个字符串相等所需删除字符的 ASCLL 值的最小和。 int main(){scanf("%s%s", s, t);n = strlen(s), m = strlen(t);memset(dp, 0x3f, sizeof dp);dp[0][0] = 0;for(int i = 1; i <= n; i++) {dp[i][0] = dp[i - 1][0] + s[i - 1];}for(int j = 1; j <= m; j++){dp[0][j] = dp[0][j - 1] + t[j - 1];}for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1];else dp[i][j] = min(dp[i - 1][j] + s[i - 1], dp[i][j - 1] + t[j - 1]);}}printf("%d\n", dp[n][m]);return 0;
}