712. Minimum ASCII Delete Sum for Two Strings

Problem

Minimum ASCII Delete Sum for Two Strings

Approach

let’s define DP[i][j] as the state for two substrings from s1 & s2, which is s1[:i + 1] & s2[:j + 1]. And DP[i][j] is the lowest cost for two such substrings. So, it’s obvious that DP[i][j] = min(DP[i - 1][j] + cost1, DP[i][j - 1] + cost2) and when s1[i] == s2[j] especially DP[i][j] = min(DP[i - 1][j - 1], DP[i][j]).

Code

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        dp[0][0] = 0;
        for(int i = 1; i <= m; i ++){
            dp[i][0] = dp[i - 1][0] + (int)s1.charAt(i - 1);
        }
        for(int i = 1; i <= n; i ++){
            dp[0][i] = dp[0][i - 1] + (int)s2.charAt(i - 1);
        }
        for(int i = 1; i <= m; i ++){
            int c1 = (int)s1.charAt(i - 1);
            for(int j = 1; j <= n; j ++){
                int c2 = (int)s2.charAt(j - 1);
                dp[i][j] = Math.min(dp[i - 1][j] + c1, dp[i][j - 1] + c2);
                if(c1 == c2 && dp[i][j] > dp[i - 1][j - 1]){
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}