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

Dear 丶 2021-09-28 19:52 207阅读 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 条评论，207人围观）

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

相关阅读

相关 leetcode 599. Minimum Index Sum of Two Lists

目录一、问题描述二、代码实现 1、暴力法 2、使用HashMap -------------------- [https://leetcode.com/p

落日映苍穹つ/ 2023年07月13日 08:19/ 0 赞/ 6 阅读

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

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

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

相关 leetcode - two-sum

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

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

相关【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 赞/ 158 阅读

相关 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 赞/ 155 阅读

相关 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 赞/ 105 阅读

相关 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 赞/ 134 阅读

相关【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 赞/ 109 阅读

相关 [Leetcode] Minimum Path Sum

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

超、凢脫俗/ 2021年12月03日 07:19/ 0 赞/ 185 阅读

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

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

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