方法思路

1. 这个问题本质上是求两个字符串的最长公共子序列(LCS)的变种
2. 我们需要找到两个字符串中不需要删除的字符，即最长公共子序列
3. 然后计算需要删除的字符的ASCII值总和，即两个字符串所有字符的ASCII值总和减去最长公共子序列中字符的ASCII值总和的两倍
4. 使用动态规划求解：
   • 定义dp[i][j]为使s1[0...i-1]和s2[0...j-1]相等所需删除字符的ASCII值最小和
   • 如果s1[i-1] == s2[j-1]，则dp[i][j] = dp[i-1][j-1]（不需要删除当前字符）
   • 否则，dp[i][j] = min(dp[i-1][j] + ASCII(s1[i-1]), dp[i][j-1] + ASCII(s2[j-1]))（删除s1[i-1]或s2[j-1]）

代码实现

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s1 = scanner.nextLine();
        String s2 = scanner.nextLine();
        
        System.out.println(minimumDeleteSum(s1, s2));
    }
    
    public static int minimumDeleteSum(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        
        // 创建dp数组，dp[i][j]表示使s1[0...i-1]和s2[0...j-1]相等所需删除字符的ASCII值最小和
        int[][] dp = new int[m + 1][n + 1];
        
        // 初始化第一行，表示s1为空时，需要删除s2中的所有字符
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j-1] + s2.charAt(j-1);
        }
        
        // 初始化第一列，表示s2为空时，需要删除s1中的所有字符
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i-1][0] + s1.charAt(i-1);
        }
        
        // 填充dp数组
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1)) {
                    // 如果当前字符相同，不需要删除
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    // 否则，选择删除s1[i-1]或s2[j-1]中ASCII值较小的一个
                    dp[i][j] = Math.min(dp[i-1][j] + s1.charAt(i-1), dp[i][j-1] + s2.charAt(j-1));
                }
            }
        }
        
        return dp[m][n];
    }
}

Python

def minimum_delete_sum(s1, s2):
    m, n = len(s1), len(s2)
    
    # 创建dp数组，dp[i][j]表示使s1[0...i-1]和s2[0...j-1]相等所需删除字符的ASCII值最小和
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 初始化第一行，表示s1为空时，需要删除s2中的所有字符
    for j in range(1, n + 1):
        dp[0][j] = dp[0][j-1] + ord(s2[j-1])
    
    # 初始化第一列，表示s2为空时，需要删除s1中的所有字符
    for i in range(1, m + 1):
        dp[i][0] = dp[i-1][0] + ord(s1[i-1])
    
    # 填充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:
                # 否则，选择删除s1[i-1]或s2[j-1]中ASCII值较小的一个
                dp[i][j] = min(dp[i-1][j] + ord(s1[i-1]), dp[i][j-1] + ord(s2[j-1]))
    
    return dp[m][n]

# 读取输入
s1 = input().strip()
s2 = input().strip()

# 计算并输出结果
print(minimum_delete_sum(s1, s2))

C++

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int minimumDeleteSum(string s1, string s2) {
    int m = s1.length();
    int n = s2.length();
    
    // 创建dp数组，dp[i][j]表示使s1[0...i-1]和s2[0...j-1]相等所需删除字符的ASCII值最小和
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    // 初始化第一行，表示s1为空时，需要删除s2中的所有字符
    for (int j = 1; j <= n; j++) {
        dp[0][j] = dp[0][j-1] + s2[j-1];
    }
    
    // 初始化第一列，表示s2为空时，需要删除s1中的所有字符
    for (int i = 1; i <= m; i++) {
        dp[i][0] = dp[i-1][0] + s1[i-1];
    }
    
    // 填充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 {
                // 否则，选择删除s1[i-1]或s2[j-1]中ASCII值较小的一个
                dp[i][j] = min(dp[i-1][j] + s1[i-1], dp[i][j-1] + s2[j-1]);
            }
        }
    }
    
    return dp[m][n];
}

int main() {
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    
    cout << minimumDeleteSum(s1, s2) << endl;
    
    return 0;
}