712. Minimum ASCII Delete Sum for Two Strings

link

Longest Common Subsequence problem (LCS)

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:

        m = len(s1)
        n = len(s2)

        dp = [[0] * (n + 1) for i in range(m + 1)]

        s1 = '#' + s1
        s2 = '#' + s2

        for i in range(1, n+1):
            dp[0][i] = dp[0][i-1] + ord(s2[i])
            
        for j in range(1, m+1):
            dp[j][0] = dp[j-1][0] + ord(s1[j])
        

        for i in range(1, m+1):
            for j in range(1, n+1):
                if s1[i] == s2[j]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j]+ord(s1[i]),dp[i][j-1]+ord(s2[j]))

        return dp[-1][-1]