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]
}