712. Minimum ASCII Delete Sum for Two Strings
給兩個strings s1、s2
透過刪掉s1、s2裡的元素讓s1和s2相等
請回傳刪掉的元素最小的ASCII sum
思路:
就dp問題
跟longest common subsequence很像
用2D的DP矩陣
其中DP[i,j]代表到s1[:i]、s2[:j]刪掉元素的最小ASCII sum
當s1[i]==s2[j]就不用刪掉
此時DP[i,j]=DP[i-1,j-1]
若s1[i]!=s2[j]則dp[i,j]=min(dp[i-1,j]+s2[i],dp[i,j-1]+s1[j])
這樣就可以得到答案了
golang code :
func minimumDeleteSum(s1 string, s2 string) int {
n, m := len(s1), len(s2)
dp1, dp2 := make([]int, n+1), make([]int, n+1)
for i := 1; i <= n; i++ {
dp1[i] = int(s1[i-1]) + dp1[i-1]
}
for i := 0; i < m; i++ {
dp2[0] = int(s2[i]) + dp1[0]
for j := 1; j <= n; j++ {
if s2[i] == s1[j-1] {
dp2[j] = dp1[j-1]
} else {
dp2[j] = min(dp1[j]+int(s2[i]), dp2[j-1]+int(s1[j-1]))
}
}
dp1 = dp2
dp2 = make([]int, n+1)
}
return dp1[n]
}