【DP】最优包含

梦里梦外; 2024-03-24 10:59 48阅读 0赞

**s b 把**

**这种DP到现在还不会做**

**篮球被在即，才发现自己居然菜成这样**

**早该44了**

题意：

![c517433dfec24fdba47a6ed6869d4407.png][]

思路：

状态设计：

设dp\[i\]\[j\]为a数组的前i个，b数组前j个，修改的最少次数

状态转移：

我居然是不会在转移上

漏了一种情况

当s\[i\]==t\[j\]时，最少修改次数为dp\[i-1\]\[j-1\]

当s\[i\]!=t\[j\]时，可以把s\[i\]变成t\[j\]，也可以把t\[j\]变成s\[i\]，这样就是dp\[i-1\]\[j-1\]+1

或者不修改s\[i\]，让s\[i-1\]和t\[j\]匹配，这样就是dp\[i-1\]\[j\]

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e3+10;
    const int mxe=1e6+10;
    const int mod=1000007;
    
    
    int n1,n2;
    int dp[mxn][mxn];
    string s,t;
    void solve(){
        cin>>s>>t;
        n1=s.size();
        n2=t.size();
        s=" "+s;
        t=" "+t;
        memset(dp,0x3f,sizeof(dp));
        dp[0][0]=0;
        for(int i=1;i<=n1;i++) dp[i][0]=0;
        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                if(s[i]==t[j]) dp[i][j]=dp[i-1][j-1];
                else dp[i][j]=min(dp[i-1][j-1]+1,dp[i-1][j]);
            }
        }
        cout<<dp[n1][n2]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[c517433dfec24fdba47a6ed6869d4407.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/c848c0a16f6b4bd0a1519e058558c4e9.png

发表评论取消回复

表情：

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

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

相关阅读

相关【DP】最优包含

s b 把这种DP到现在还不会做篮球被在即，才发现自己居然菜成这样早该44了题意： ![c517433dfec24fdba47a6ed6869d4407.pn

梦里梦外;/ 2024年03月24日 10:59/ 0 赞/ 49 阅读

相关 nyoj 536 开心的mdd(最优矩阵链乘)dp

开心的mdd 时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述 himdd有一天闲着无聊，随手拿了一本书，随手翻到一页，上面描述了一个

不念不忘少年蓝@/ 2024年02月17日 19:32/ 0 赞/ 38 阅读

相关 DP：最长有效括号

DP：最长有效括号问题： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0c

Love The Way You Lie/ 2023年10月06日 16:51/ 0 赞/ 71 阅读

相关局部最优到全局最优

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

谁借莪１个温暖的怀抱￠/ 2023年05月21日 15:19/ 0 赞/ 12 阅读

相关 341 最优贸易（单元最短路径 + dp）

1. 问题描述： C 国有 n 个大城市和 m 条道路，每条道路连接这 n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行

我就是我/ 2022年08月28日 05:44/ 0 赞/ 181 阅读

相关 HDU2833-最短路+dp

WuKong Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Ot

绝地灬酷狼/ 2022年07月11日 13:10/ 0 赞/ 162 阅读

相关 dp 最优矩阵乘法

该题题意如下描述有若干个矩阵\{Ai\}，元素都为整数且已知矩阵大小。如果要计算所有矩阵的乘积A1 \ A2 \ A3 .. Am，最少要多少次整数乘法？

小咪咪/ 2022年06月13日 08:42/ 0 赞/ 199 阅读

相关 DP-求最大值求最优解

Description 分配了8个任务,时间不冲突的情况下,挣得工资最多 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdG

悠悠/ 2022年04月15日 07:08/ 0 赞/ 258 阅读

相关 uva10304 Optimal Binary Search Tree（最优二叉排序树区间dp）

题意：给n个符号建立一棵排序二叉树，给出每个符号检索的频率，要求从检索的次数最小。分析：《训练指南》P64，很详细。代码： include<bits

- 日理万妓/ 2021年12月13日 20:13/ 0 赞/ 213 阅读

相关 dp:最短编辑距离

最短编辑距离问题：详细解释（[https://blog.csdn.net/ac540101928/article/details/52786435][https_blog.cs

秒速五厘米/ 2021年11月08日 18:04/ 0 赞/ 332 阅读