#
# @lc app=leetcode.cn id=712 lang=python3
#
# [712] 两个字符串的最小ASCII删除和
#
# https://leetcode-cn.com/problems/minimum-ascii-delete-sum-for-two-strings/description/
#
# algorithms
# Medium (65.79%)
# Likes:    204
# Dislikes: 0
# Total Accepted:    10.1K
# Total Submissions: 15.3K
# Testcase Example:  '"sea"\n"eat"'
#
# 给定两个字符串s1, s2，找到使两个字符串相等所需删除字符的ASCII值的最小和。
# 
# 示例 1:
# 
# 
# 输入: s1 = "sea", s2 = "eat"
# 输出: 231
# 解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
# 在 "eat" 中删除 "t" 并将 116 加入总和。
# 结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。
# 
# 
# 示例 2:
# 
# 
# 输入: s1 = "delete", s2 = "leet"
# 输出: 403
# 解释: 在 "delete" 中删除 "dee" 字符串变成 "let"，
# 将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。
# 结束时，两个字符串都等于 "let"，结果即为 100+101+101+101 = 403 。
# 如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。
# 
# 
# 注意:
# 
# 
# 0 < s1.length, s2.length <= 1000。
# 所有字符串中的字符ASCII值在[97, 122]之间。
# 
# 
#

# @lc code=start
class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        ## 实际题目要求的就是ASCII值最大的公共子序列
        # 而不是最长的，所以下面的原本的+1操作就变成 +ASSCII值了
        n1, n2 = len(s1), len(s2)
        dp = [[0 for _ in range(n2+1)] for _ in range(n1+1)]
        for i in range(1, n1+1):
            for j in range(1, n2+1):
                if s1[i-1] == s2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + ord(s1[i-1])
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        ord_sum1 = sum([ord(item) for item in s1])
        ord_sum2 = sum([ord(item) for item in s2])
        return ord_sum1 + ord_sum2 - 2*dp[n1][n2]
# @lc code=end

