題目

https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/

題解

經(jīng)典的 暴力遞歸 -> 傻緩存 -> DP

實(shí)際上是找兩個(gè)字符串的 最大ASCII碼和 的公共子序列，然后用總的 ASCII 之和減一下就行了。可以參考兩個(gè)字符串的最長(zhǎng)公共子序列，只不過(guò)取 max 的依據(jù)不同，一個(gè)是 ASCII 碼相加，一個(gè)是取長(zhǎng)度。

class Solution {public int minimumDeleteSum(String s1, String s2) {int sum = 0;for (int i = 0; i < s1.length(); i++) {sum += s1.charAt(i);}for (int i = 0; i < s2.length(); i++) {sum += s2.charAt(i);}// Approach 1: Recursive, Brute Force // return sum - process1(s1, s2, 0, 0);// Approach 2: Recursion with Memoization // int[][] dp = new int[s1.length() + 1][s2.length() + 1]; // for (int i = 0; i < dp.length - 1; i++) { // for (int j = 0; j < dp[0].length - 1; j++) { // dp[i][j] = -1; // } // } // return sum - process2(s1, s2, 0, 0, dp);// Approach 3: Dynamic Programmingint[][] dp = new int[s1.length() + 1][s2.length() + 1];for (int i = s1.length() - 1; i >= 0; i--) {for (int j = s2.length() - 1; j >= 0; j--) {int p1 = s1.charAt(i) == s2.charAt(j) ? dp[i + 1][j + 1] + s1.charAt(i) + s2.charAt(j) : 0;int p2 = dp[i + 1][j];int p3 = dp[i][j + 1];dp[i][j] = Math.max(p1, Math.max(p2, p3));}}return sum - dp[0][0];}// public int process2(String s1, String s2, int i, int j, int[][] dp) { // if (dp[i][j] >= 0) return dp[i][j]; // int p1 = s1.charAt(i) == s2.charAt(j) ? process2(s1, s2, i + 1, j + 1, dp) + s1.charAt(i) + s2.charAt(j) : 0; // int p2 = process2(s1, s2, i + 1, j, dp); // int p3 = process2(s1, s2, i, j + 1, dp); // dp[i][j] = Math.max(p1, Math.max(p2, p3)); // return dp[i][j]; // }// public int process1(String s1, String s2, int i, int j) { // if (i == s1.length() || j == s2.length()) return 0; // int p1 = s1.charAt(i) == s2.charAt(j) ? process1(s1, s2, i + 1, j + 1) + s1.charAt(i) + s2.charAt(j) : 0; // int p2 = process1(s1, s2, i + 1, j); // int p3 = process1(s1, s2, i, j + 1); // return Math.max(p1, Math.max(p2, p3)); // } }

總結(jié)

以上是生活随笔為你收集整理的leetcode 712. Minimum ASCII Delete Sum for Two Strings | 712. 两个字符串的最小ASCII删除和（暴力递归-＞傻缓存-＞DP）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。