LeetCode 712 Minimum ASCII Delete Sum for Two Strings

    
        标签：
        
            动态规划问题
        
            LeetCode
        
    发布于：2022-02-16 14:18:13
    编辑于：2022-02-16 14:46:13
    浏览量：968

概述

https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/

动态规划法

极值问题，该怎么办不用我多说了吧？

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        vector<vector<int>> dp(s1.size(), vector<int>(s2.size(), -1));
        return helper(dp, s1, s2, 0, 0);
    }
    
    int helper(vector<vector<int>>& dp, string& s1, string& s2, int i, int j) {
        if (i == s1.size()) return restSum(s2, j);
        if (j == s2.size()) return restSum(s1, i);
        if (dp[i][j] != -1) return dp[i][j];
        if (s1[i] == s2[j]) {
            dp[i][j] = helper(dp, s1, s2, i + 1, j + 1);
        } else {
            dp[i][j] = min(s1[i] + helper(dp, s1, s2, i + 1, j), s2[j] + helper(dp, s1, s2, i, j + 1));
        }
        return dp[i][j];
    }
    
    int restSum(string& s, int i) {
        int sum = 0;
        while (i < s.size()) {
            sum += s[i++];
        }
        return sum;
    }
};

Links: leetcode-712-minimum-ascii-delete-sum-for-two-strings