首页 > 其他分享 >代码随想录训练营第五十六天 | 动态规划

代码随想录训练营第五十六天 | 动态规划

时间:2022-12-08 04:00:08浏览次数:70  
标签:String int 训练营 随想录 length word1 word2 第五十六 dp

 今天是第五十六天,是距离问题的动态规划  

583. 两个字符串的删除操作 

class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();

        int[][] dp = new int[n+1][m+1];

        for(int i =1; i<=n ;i++){
            for(int j = 1; j<=m; j++){
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                else{
                    dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        return m + n - dp[n][m]*2;
    }
}

dp的数组存储公共的部分,那么其他的部分就是总长减去每个字符串相同的部分,就是不同的,需要删除的部分了。

72. 编辑距离 

class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        int[][]dp = new int[n+1][m+1];
        
        for(int i = 1; i<=n; i++){
            dp[i][0] = dp[i-1][0]+1;
        }
        for(int j = 1; j<=m; j++){
            dp[0][j] = dp[0][j-1]+1;
        }

        for(int i = 1; i<=n; i++){
            for(int j = 1; j<=m; j++){
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }
                else{
                    dp[i][j] = Math.min(Math.min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1])+1;
                }
            }
        }
        return dp[n][m];
    }
}

和上一道题很像,这个dp是记录最小删除次数的。

 

今天的题是路径删除问题,沿用的依旧是dp数组的模版

标签:String,int,训练营,随想录,length,word1,word2,第五十六,dp
From: https://www.cnblogs.com/catSoda/p/16965071.html

相关文章

  • 代码随想录训练营第五十五天 | (动态规划)
     今天是第五十五天,依旧是动态规划问题的子序列问题 392.判断子序列 classSolution{publicbooleanisSubsequence(Strings,Stringt){intn......
  • 代码随想录Day37
    LeetCode701.二叉搜索树种的插入操作给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证,新值和原始二叉搜索......
  • 代码随想录算法训练营Day16| 104. 二叉树的最大深度、559.n叉树的最大深度、111. 二叉
    代码随想录算法训练营Day16|104.二叉树的最大深度、559.n叉树的最大深度、111.二叉树的最小深度、222.完全二叉树的节点个数104.二叉树的最大深度104.二叉树的最大......
  • 代码随想录Day36
    LeetCode235.二叉搜索树的最近公共祖先给定一个二叉搜索树,找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树T的两个结点p、q,最......
  • 代码随想录——栈与队列
    用栈实现队列题目简单把pop()和peek()中可复用的部分提取出来classMyQueue{Stack<Integer>stackIn;Stack<Integer>stackOut;/**Initialize......
  • 代码随想录Day35
    LeetCode236.二叉树的最近公共祖先给定一个二叉树,找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树T的两个结点p、q,最近公共祖......
  • 代码随想录训练营第五十三天 | 动态规划
    今天是代码随想录的第五十三天,今天依旧是子集问题  ●  1143.最长公共子序列 classSolution{publicintlongestCommonSubsequence(Stringtext1,......
  • 【MindStudio训练营第一季】MindStudio Profiling随笔
    MindStudioProfiler简介AscendAI处理器是一款面向AI业务应用的高性能集成芯片,包含AICPU、ACore、AIVectorCore等计算单元来提升AI任务的运算性能。基于AscendAI处理......
  • 【MindStudio训练营第一季】MindStudio 专家系统随笔
    简介专家系统(MindstudioAdvisor)是用于聚焦模型和算子的性能调优Top问题,识别性能瓶颈,重点构建瓶颈分析、优化推荐模型,支撑开发效率提升的工具。专家系统当前已经支持针对......
  • 【MindStudio训练营第一季】MindStudio 专家系统随笔
    简介专家系统(MindstudioAdvisor)是用于聚焦模型和算子的性能调优Top问题,识别性能瓶颈,重点构建瓶颈分析、优化推荐模型,支撑开发效率提升的工具。专家系统当前已经支持针......