712. 两个字符串的最小ASCII删除和
示例 1:
输入: s1 = "sea", s2 = "eat" 输出: 231 解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。 在 "eat" 中删除 "t" 并将 116 加入总和。 结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。
示例 2:
输入: s1 = "delete", s2 = "leet" 输出: 403 解释: 在 "delete" 中删除 "dee" 字符串变成 "let"， 将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。 结束时，两个字符串都等于 "let"，结果即为 100+101+101+101 = 403 。 如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。
思路：
对于本题，有两种解决办法，一种是直接求最小的删除和，一种是求公共子序列中ascii最大的和，这样再和字符串的ascii相减就是结果。
对于直接求最小的删除和，dp[i][j]为s1的0到i和s2的0到j的最小删除和，此时dp的组成是：
s1[i]==s2[j]，则dp[i][j]=dp[i-1][j-1],
s1[i]!=s2[j],则dp[i][j]=min(dp[i][j-1]+s2[j],dp[i-1][j]+s1[i])。此时可以分为三种情况，保s1[i],删s2[j],保s2[j]，删s1[i],删s1[i]和s2[j]，其中第一种情况和第三中情况共同构成了dp[i][j-1]+s2[j],第二种和第三中情况共同构成dp[i-1][j]+s1[i]。取其中的最小值即可。（比如删s2[j]，则dp[i][j-1]中一定是没有s2[j]，但s1[i]可能有可能没有，无法确定是否是构成当前最小ascii的，但无论怎样都包含在情况一和情况三中）
初始化：
i==0时，则对于s2的第j个元素进入，进一个就得删一个，因此dp[0][j]=dp[0][j-1]+s2[j]，对j==0同理。
思路2：求公共子序列中ascii最大的和，
此时dp[i][j]为s1的0到i和s2的0到j的公共子序列的最大ascii和
s1[i]==s2[j]，则dp[i][j]=dp[i-1][j-1]+s1[i],
s1[i]!=s2[j],则dp[i][j]=max(dp[i][j-1],dp[i-1][j])。此时可以分为三种情况，s1[i]在dp[i][j]而s2[j]不在,s2[j在而s1[i]不在,s1[i]和s2[j]都不在，其中第一种情况和第三中情况共同构成了dp[i][j-1],第二种和第三中情况共同构成dp[i-1][j]。取其中的最小值即可。
初始化：
此时i==0时，唯一的公共字符串是空串，因此dp[0][j]全为0，对j==0同理。
class Solution {
public:int minimumDeleteSum(string s1, string s2) {int n1=s1.size(),n2=s2.size();vector<vector<int>>dp(n1+1,vector<int>(n2+1));s1=" "+s1,s2=" "+s2;for(int i=1;i<=n1;i++){dp[i][0]=s1[i]+dp[i-1][0];}for(int j=1;j<=n2;j++){dp[0][j]=dp[0][j-1]+s2[j];}for(int i=1;i<=n1;i++){for(int j=1;j<=n2;j++){if(s1[i]==s2[j]){dp[i][j]=dp[i-1][j-1];}else{dp[i][j]=min(dp[i-1][j]+s1[i],dp[i][j-1]+s2[j]);}}}return dp[n1][n2];// for(int i=1;i<=n1;i++)
// {
// for(int j=1;j<=n2;j++)
// {
// if(s1[i]==s2[j])
// {
// dp[i][j]=dp[i-1][j-1]+s1[i];
// }
// else
// {
// dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
// }
// }
// }// int ret=0;
// for(int i=1;i<=n1;i++)
// {
// ret+=s1[i];
// }
// for(int i=1;i<=n2;i++)
// {
// ret+=s2[i];
// }
// return ret-2*dp[n1][n2];}
};