100天代码挑战：DAY12

LeetCode 712. 两个字符串的最小ASCII删除和

给定两个字符串s1, s2，找到使两个字符串相等所需删除字符的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 的结果，比答案更大。
</pre>

注意:

• 0 < s1.length, s2.length <= 1000。
• 所有字符串中的字符ASCII值在[97, 122]之间。

我的答案：

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int map[s1.length()+1][s2.length()+1];
        
        map[0][0] = 0;
        int i,j;
        
        for(i=1; i<=s1.length();i++){
            map[i][0] = map[i-1][0] + (int)s1[i-1];
        }
        for(i=1; i<=s2.length();i++){
            map[0][i] = map[0][i-1] + (int)s2[i-1];
        }
        
        for(i=1; i<=s1.length();i++){
            for(j=1; j<=s2.length(); j++){
                if(s1[i-1] == s2[j-1]) {
                    map[i][j] = map[i-1][j-1];
                }
                else{
                    map[i][j] = min(map[i-1][j]+(int)s1[i-1], map[i][j-1]+(int)s2[j-1]);
                }
            }
        }
        
        return map[i-1][j-1];
    }
};

LeetCode 343. 整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

**说明: **你可以假设n不小于 2 且不大于 58。

我的答案：

class Solution {
public:
    int integerBreak(int n) {
        int res = 1;
        if(n%3 == 0){
            if(n == 3) return 2;
            for(int i=0; i<n/3; i++){
                res *= 3;
            }
        }
        else if(n%3 == 1){
            for(int i=0; i<n/3-1; i++){
                res *= 3;
            }
            res *= 4;
        }
        else if(n%3 == 2){
            if(n == 2) return 1;
            for(int i=0; i<n/3; i++){
                res *= 3;
            }
            res *= 2;
        }
        return res;
    }
};