图片. PNG
C++ code:
- // 我们建立一个二维数组 dp, 其中 dp[i][j] 表示字符串 s1 的前 i 个字符和字符串 s2 的前 j 个字符变相等所要删除的字符的最小 ASCII 码累加值.
- //dp 还是多一圈, 如果不一样取当前上 + s1 / 左 + s2 最小值
- int minimumDeleteSum(string s1, string s2) {
- int m=s1.size();
- int n=s2.size();
- vector<vector<int>> dp(m+1,vector<int>(n+1,0));
- for(int i=1;i<=m;i++){
- dp[i][0]=dp[i-1][0]+s1[i-1];
- }
- for(int i=1;i<=n;i++)
- dp[0][i]=s2[i-1]+dp[0][i-1];
- for(int i=1;i<=m;i++){
- for(int j=1;j<=n;j++){
- dp[i][j]=(s1[i-1]==s2[j-1])? dp[i-1][j-1]:min(dp[i][j-1]+s2[j-1], dp[i-1][j]+s1[i-1] );
- }
- }
- return dp[m][n];
- }
来源: http://www.jianshu.com/p/fcb85c61dd3f