dp5-力扣-java

标签: 动态规划  

 解题思路:转化为求两个字符串最大公共子序列的问题

class Solution {
    public int minDistance(String word1, String word2) {
        int m=word1.length();
        int n=word2.length();
        int [][]dp=new int[m+1][n+1];
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;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-1][j],dp[i][j-1]);
                }
            }
        }
        return m+n-2*dp[m][n];
    }
}

 

版权声明:本文为a716121原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/a716121/article/details/106448437

智能推荐

python+opencv实现图像拼接

任务 拍摄两张图片去除相同部分,拼接在一起 原图 结果 步骤 读取两张图片 使用sift检测关键点及描述因子 匹配关键点 处理并保存关键点 得到变换矩阵 图像变换并拼接 代码实现 扩展 这里对右边图像进行变换,右边变得模糊,可以修改代码对左边图像变换 这里只有两张图片拼接,可以封装实现多张图片拼接 可以修改代码实现上下图片的拼接...

python_sklearn机器学习算法系列之AdaBoost------人脸识别(PCA,决策树)

          注:在读本文之前建议读一下之前的一片文章python_sklearn机器学习算法系列之PCA(主成分分析)------人脸识别(k-NearestNeighbor,KNN)         本文主要目的是通过一个简单的小...

memmove函数与memcpy函数的模拟实现

memmove函数和memcpy函数都是在内存复制任意类型的,但是它俩也有区别。当源区域和目标区域有重复的,memmove函数会复制缓冲区重叠的部分,而memcpy相反,会报出未知错误。 下面给出两个函数的实现 首先,memmove函数。 实现的基本原理如下图。 具体代码如下: memcpy函数的实现很简单,就直接给出源代码了...

SpringFramework核心 - IOC容器的实现 - 总结

1. 概述 把Spring技术内幕第一章和第二章过了一遍,也做了一些笔记, 对IOC容器的实现有了一定皮毛理解,现在跟着源码再过一遍总结一下IOC容器的初始化,Bean的初始化的过程,做一下总结 ① IOC容器和简单工厂模式 在开始之前,先想想我们平时是怎么使用IOC容器为我们管理Bean的,假设我们要把下面的User类交给IOC容器管理 我们不想关心如何创建一个User对象实例的,仅仅在需要他的...

猜你喜欢

Python和Django的安装

个人博客导航页(点击右侧链接即可打开个人博客):大牛带你入门技术栈  一、下载并安装Python Python 官方下载地址:http://www.python.org/ftp/python/ 我们这里选择的是 Python 2.7.2 。虽然目前最新版是Python 3.2.2, 但是Django目前还不支持 Python 3.2.2。 安装步骤很简单,双击安装包开...

OpenStack代码贡献初体验

为什么80%的码农都做不了架构师?>>>     OpenStack如今已成为开源云平台中的明星项目,得到广泛关注。OpenStack的优秀出众依赖于众多开发者的努力,在享受其带来的便利与快捷的同时,为其做一份贡献也是一个开发者的义务。  在前段时间的OpenStack的测试过程中,我发现Nova项目中的一个Bug,于是向社区提交了Bug报...

SQL Server之8:sql查询每个学生得分最高的两门课

这是一道面试题,今天有空把它记下来,以后遇到此类问题作个参考!刚一看到这个题目,估计好多人都会想到关键字top,其实这里用到的关键字是partition, 好了,先看看表结构,及数据吧!     接下来看一看partition的功能,执行语句   结果如下:   到这里一目了然知道最终结果了!   View Code     &...

vue-video-player 浏览器缩放

文章目录 前言 一、vue-video-player的封装 二、调用 1. 引入 2. vue template代码 2. 主要js代码 效果 前言 此篇是在上一次《[Vue 播放rtmp直播流]》基础之上的更新及补充;近期接到客户需求,需要在视频流上显示额外的信息;当然,视频流上叠加信息可以通过canvas来完成(透明canvas实现),但是在测试的过程中发现,当浏览器缩放时,叠加的图层信息与初...

Hibernate简单实例:数据库驱动配置及数据的输入

前言:本次使用的hibernate框架为idea自动创建的版本:5.3.7.Final   本机的mysql版本为 8.0.11  下载的mysql 驱动程序版本为 mysql-connector-java-8.0.11.jar 一、Hibernate开发的环境搭建 1.使用idea工具创建hibernate项目 然后一路next,按照自己的需要填写项目名称,项目存放...