712.js

//Given two strings s1, s2, find the lowest ASCII sum of deleted characters to m
//ake two strings equal.
//
// Example 1:
//
//Input: s1 = "sea", s2 = "eat"
//Output: 231
//Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the
//sum.
//Deleting "t" from "eat" adds 116 to the sum.
//At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum pos
//sible to achieve this.
//
//
//
// Example 2:
//
//Input: s1 = "delete", s2 = "leet"
//Output: 403
//Explanation: Deleting "dee" from "delete" to turn the string into "let",
//adds 100[d]+101[e]+101[e] to the sum.  Deleting "e" from "leet" adds 101[e] to
// the sum.
//At the end, both strings are equal to "let", and the answer is 100+101+101+101
// = 403.
//If instead we turned both strings into "lee" or "eet", we would get answers of
// 433 or 417, which are higher.
//
//
//
// Note:
// 0 < s1.length, s2.length <= 1000.
// All elements of each string will have an ASCII value in [97, 122].
// Related Topics 动态规划
// 👍 218 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * @param {string} s1
 * @param {string} s2
 * @return {number}
 */
var minimumDeleteSum = function (s1, s2) {
  const dp = new Array(s1.length + 1).fill(0)
    .map(_ => new Array(s2.length + 1).fill(0));

  function dfs(i, j) {
    if (i == 0 && j == 0) return 0;

    if (dp[i][j]) {
      return dp[i][j];
    }

    let s1c = s1.charCodeAt(i - 1);
    let s2c = s2.charCodeAt(j - 1);

    let ar = [];
    if (s1c == s2c) {
      ar.push(dfs(i - 1, j - 1));
    }

    if (i > 0) {
      ar.push(dfs(i - 1, j) + s1c);
    }

    if (j > 0) {
      ar.push(dfs(i, j - 1) + s2c);
    }

    let r = Math.min(...ar);
    dp[i][j] = r;
    return r;
  }

  return dfs(s1.length, s2.length);
  // return dp[s1.length][s2.length];
};
//leetcode submit region end(Prohibit modification and deletion)

const r = minimumDeleteSum('sea', 'eat');
console.log(`r: ` + JSON.stringify(r, null, 4) + '\n')