[leetcode]动态规划之Minimum ASCII Delete Sum for Two Strings

Dear 丶 2021-09-28 19:52 181阅读 0赞

### 动态规划之Minimum ASCII Delete Sum for Two Strings ###

*  题目
 *  思考
 *  答案

# 题目 #

[leetcode入口][leetcode]

# 思考 #

这道题的特征：**两个字符串**，**dp**  
对于两个字符串的这种问题，一般dp用**二维数组**表示，dp\[i\]\[j\]一般表示两个字符串前i个和前j个字符所满足的性质

刚开始做这道题，以为和删去字符的ASCII值有关，后来发现其实和求**编辑距离没什么两样**

# 答案 #

class Solution { 
    public:
        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 j=1;j<=n;j++) dp[0][j]=dp[0][j-1]+s2[j-1];
            
            for(int i=1;i<=m;i++){ 
                dp[i][0]=dp[i-1][0]+s1[i-1];
                
                for(int j=1;j<=n;j++){ 
                    if(s1[i-1]==s2[j-1]){ 
                        dp[i][j]=dp[i-1][j-1];
                    }
                    else{ 
                        dp[i][j]=min(dp[i-1][j]+s1[i-1],dp[i][j-1]+s2[j-1]);
                    }
                }
            }
            
            return dp[m][n];
            
            
        }
    };

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

发表评论取消回复

表情：

评论列表（有 0 条评论，181人围观）

还没有评论，来说两句吧...

相关阅读

相关 Minimum ASCII Delete Sum for Two Strings（C++两个字符串的最小ASCII删除和）

解题思路： (1)动态规划 class Solution { public: int minimumDeleteSum(string s1,

拼搏现实的明天。/ 2023年01月16日 06:34/ 0 赞/ 86 阅读

相关 leetcode - two-sum

文章目录 Q A - 1 暴力破解 Q -2 查找表法 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk

偏执的太偏执、/ 2022年12月29日 09:42/ 0 赞/ 93 阅读

相关 leetcode 599. Minimum Index Sum of Two Lists

1.题目 Suppose Andy and Doris want to choose a restaurant for dinner, and they both hav

浅浅的花香味﹌/ 2022年06月15日 09:00/ 0 赞/ 94 阅读

相关【LeetCode】Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a

电玩女神/ 2022年06月10日 05:08/ 0 赞/ 136 阅读

相关 leetcode 64. Minimum Path Sum DP动态规划

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom

逃离我推掉我的手/ 2022年06月09日 11:42/ 0 赞/ 122 阅读

相关 leetcode 712. Minimum ASCII Delete Sum for Two Strings 动态规划DP的典型变形题

Given two strings s1, s2, find the lowest ASCII sum of deleted characters to make two st

古城微笑少年丶/ 2022年06月03日 08:50/ 0 赞/ 85 阅读

相关 leetcode 583. Delete Operation for Two Strings 问题转换+最长公共子串 + DP动态规划

Given two words word1 and word2, find the minimum number of steps required to make word1

Myth丶恋晨/ 2022年06月03日 04:41/ 0 赞/ 110 阅读

相关【Leetcode】583.Delete Operation for Two Strings

Delete Operation for Two Strings Given two words word1 and word2, find the minimum nu

左手的ㄟ右手/ 2022年04月14日 21:16/ 0 赞/ 83 阅读

相关【Leetcode】64. Minimum Path Sum（动态规划）

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom

「爱情、让人受尽委屈。」/ 2022年02月27日 13:34/ 0 赞/ 137 阅读

相关 [leetcode]动态规划之Minimum ASCII Delete Sum for Two Strings

动态规划之Minimum ASCII Delete Sum for Two Strings 题目思考答案题目 [leetcode入口][l

Dear 丶/ 2021年09月28日 19:52/ 0 赞/ 182 阅读