电子政务 网站建设bing搜索国内版

两个字符串s1, s2, 删除其中的字母使s1和s2相等。
问删除字母的最小ASCII码之和是多少。

思路：

DP

先考虑极端的情况，s1为空，那么要想达到s2和s1相等，就要把s2中的字母删完，
ASCII码之和就是s2中所有字母的ASCII码之和。
同理s2为空的情况。

现在来遍历s1和s2, s1的下标记为 i , s2的下标记为 j.
记dp[ i ][ j ]表示s1, s2分别遍历到i, j时删除字母的ASCII码之和。

如果s1[ i ] == s2[ j ], 字母相等，不需要删除，那么状态保持在前一状态，
也就是dp[ i ][ j ] = dp[i-1][j-1].

如果字母不相等，要么删除s1[ i ], 要么删除s2[ j ].
删除s1[ i ]的ASCII码: dp[i-1][ j ] + s1[ i ]
删除s2[ j ]的ASCII码: dp[i][ j+1 ] + s2[ j ]
取两者中较小的一个给dp[ i ][ j ]

最后返回dp[s1.length][s2.length]

    public int minimumDeleteSum(String s1, String s2) {char[] chs1 = s1.toCharArray();  //计算更快char[] chs2 = s2.toCharArray();int n1 = chs1.length;int n2 = chs2.length;int[][] dp = new int[n1+1][n2+1];//注意下面的i,j是遍历到的字符串长度，下标需要-1//s2长度为0时，s1达到长度为0需要删除字母的ASCII码之和for(int i = 1; i <= n1; i++) dp[i][0] = dp[i-1][0]+chs1[i-1];//s1长度为0时，s2达到长度为0需要删除字母的ASCII码之和for(int i = 1; i <= n2; i++) dp[0][i] = dp[0][i-1] + chs2[i-1];for(int i = 1; i <= n1; i++) {for(int j = 1; j <= n2; j++) {if(chs1[i-1] == chs2[j-1]) { //字符相等，不需要删除字母，保持前一状态dp[i][j] = dp[i-1][j-1];} else {//删除s1的一个字母或者删除s2的一个字母，取较小dp[i][j] = Math.min(dp[i-1][j]+chs1[i-1], dp[i][j-1]+chs2[j-1]); }}}return dp[n1][n2];}