第33天。
今天的题目是Minimum ASCII Delete Sum for Two Strings:
一道动态规划的问题,而且挺常规的。这道题的动规方程如下:
$$ dp[i, j] = \left{ \begin{aligned} \sum_{k=0}^{j} s2[k] & ,& i == 0 \ \sum_{k=0}^{i} s1[k] & ,& j == 0 \ dp[i-1, j-1] & ,& s1[i] == s2[j] \ min{dp[i-1][j] + s1[i], dp[i][j-1] + s2[j] } & ,& s1[i] == s2[j] \end{aligned} \right. $$
其中d[i, j]
表示字符串s1[0, i)
和字符串s2[0, j)
的最小删除ASCII之和。根据动规方程可以写出如下代码: