【算法心得】二维dp的状态转移狂练

LCS：

LCS变式：使两个字符串变成一样的，删除的和最小
https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/

建表

$m\ast n$ or $(m+1)\ast (n+1)$？

感觉$(m+1)\ast (n+1)$的好想一些，以后还是都以$(m+1)\ast (n+1)$建表吧

填dp[0][0]

LCS

0

删除和最小

0

填dp[0][j]

LCS

全0

删除和最小

s2[j]+dp[0][j-1]

填dp[i][j]

LCS

s1[i]==s2[j] ? dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1])

删除和最小

s1[i]==s2[j] ? dp[i-1][j-1] : min(dp[i-1][j]+s1[i] , dp[i][j-1]+s2[j])

矫正

注意下标，i的有效值从1到n，对应数组元素的0到n-1