2026-01-10 12:50:38 +0300 MSK

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        length1, length2 = len(s1), len(s2)
        dp = [[-1] * (length2 + 1) for _ in range(length1 + 1)]
        inf = float("inf")

        def dfs(i: int, j: int) -> int:
            if dp[i][j] != -1:
                return dp[i][j]
            elif i == length1:
                res = sum(ord(char) for char in s2[j:])
            elif j == length2:
                res = sum(ord(char) for char in s1[i:])
            else:
                char1, char2 = ord(s1[i]), ord(s2[j]) 
                res = min(char1 + dfs(i + 1, j), char2 + dfs(i, j + 1))
                if char1 == char2:
                    res = min(res, dfs(i + 1, j + 1))
            dp[i][j] = res
            return res
    
        return dfs(0, 0)