开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 腾讯笔试题 -- 动态规划之两个字符串的最长公共子序列 -> 正文阅读

[数据结构与算法]腾讯笔试题 -- 动态规划之两个字符串的最长公共子序列

📢📢📢📣📣📣

哈喽！大家好，我是【Bug 终结者】 ，【CSDN新星创作者】🏆，阿里云技术博主🏆，51CTO人气博主🏆，INfoQ写作专家🏆

一位上进心十足，拥有极强学习力的【Java领域博主】😜😜😜

🏅【Bug 终结者】博客的领域是【面向后端技术】的学习，未来会持续更新更多的【后端技术】以及【学习心得】。 偶尔会分享些前端基础知识，会更新实战项目，面向企业级开发应用！
🏅 如果有对【后端技术】、【前端领域】感兴趣的【小可爱】，欢迎关注【Bug 终结者】💞💞💞

?????? 感谢各位大可爱小可爱！ ??????

在这里插入图片描述

一、什么是动态规划？

动态规划（英语：Dynamic programming，简称 DP），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

有点抽象了，下面大致解释一下意思

动态规划其实就是，给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决。然后呢，把子问题答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法。

动态规划核心思想

动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。

二、动态规划的好处

减少了计算量，随着段数的增加，计算量大大减少。
计算中得到了很多有用的中间过程，不仅得到了出发点到终点的最短路径，而且得到了中间各点到终点的最短路径。
动态规划可以得出一系列解，算法清晰简便

动态规划的好处就是：可以大大提高系统的性能，使程序得到非常显著的性能提升！

三、题目说明

给定两个字符串，求解这两个字符串的最长公共子序列（Longest Common Sequence）。

比如字符串1：ABCFGR；字符串2：ABFR2

则这两个字符串的最长公共子序列长度为4，最长公共子序列是：ABFR

四、思路分析

下图为子序列

在这里插入图片描述

下图是两个序列中最长的子序列

在这里插入图片描述

思路分析

首先我们假设给定的字符串如下

String str1 = "abcefg";
String str2 = "acdg";

我们提取出每个序列的最后一位进比较是否相等，如果相等，那就拿出来，每次计算出来后再次累加上相等的序列

String str1 = "abcefg";
String str2 = "acdg";

//提取出来后如下

"g";
"g";

然后我们提取出除了最后一位后的所有字符，进行依次比较，递归实现比较

String str1 = "abcefg";
String str2 = "acdg";

"abce"
"acd"
//最后一位字符比较，如果不同，那么先去掉，直接比较下一个，依次比较，如果相同，那就累加之前存的相同字符，最后执行完毕后进行return结果

五、递归实现

思路我们大概都知道了，就是一个一个的遍历比较是否相同，相同就累加，不同就去除，进行下一次比较！

?核心源码

现在上代码！

package com.wanshi.test;

import org.junit.Test;

public class Test3 {

    @Test
    public void test() {
        String str1 = "新增本土新冠肺炎确诊病例322例和无症状感染者19660例";
        String str2 = "上海新增本土新冠肺炎确诊病例322例，无症状感染者19660例";
        long start = System.currentTimeMillis();
        String res = lcs(str1, str2);
        long end = System.currentTimeMillis();
        System.out.println("res："+res);
        System.out.println("执行时间：" + (end - start));
    }

    /**
     * 递归计算两个序列的最长公共子序列并返回结果
     * @param str1  第一个序列
     * @param str2  第二个序列
     * @return  res
     */
    private String lcs(String str1, String str2) {
        //最后的结果存储在此局部变量内
        String lcsRes = "";

        //如果str1包含str2，直接返回str2即可
        if (str1.contains(str2)) {
            return str2;
        }
        //如果str2包含str1，直接返回str1即可
        if (str2.contains(str1)) {
            return str1;
        }

        //边界判断，如果没有数据直接返回结果即可
        if (str1.length() <= 0 || str2.length() <= 0) {
            return lcsRes;
        }

        //截取最后一位字符
        String str1Last = str1.substring(str1.length()-1);
        String str2Last = str2.substring(str2.length()-1);

        //截取除了最后一位字符后剩余的字符
        String str1Content = str1.substring(0, str1.length()-1);
        String str2Content = str2.substring(0, str2.length()-1);

        //判断第一位字符是否相同，忽略大小写判断
        if (str1Last.equalsIgnoreCase(str2Last)) {
            lcsRes = lcs(str1Content, str2Content) + str1Last;
        } else {
            //比较剩余的内容并存储
            String strRes1 = lcs(str1Content, str2);
            String strRes2 = lcs(str2Content, str1);

            if (strRes1.length() > strRes2.length()) {
                lcsRes = strRes1;
            } else {
                lcsRes = strRes2;
            }
        }
        return lcsRes;
    }
}

??执行效果

在这里插入图片描述

??递归实现的缺点

大大的降低了系统的性能，降低了可用性
执行时间太长，健壮性不好

使用递归实现，是一层一层往里走，执行，所以执行过程比较多，就好比俄罗斯套娃，一层套一层，最后一层一层返回，执行效率极低！

六、递归+动态规划实现

优化代码，采用动态规划的方式解决！

?核心源码

package com.wanshi.test;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

public class Test3 {

    @Test
    public void test() {
        String str1 = "新增本土新冠肺炎确诊病例322例和无症状感染者19660例";
        String str2 = "上海新增本土新冠肺炎确诊病例322例，无症状感染者19660例";
        //加入HashMap存储子数据，加缓存，如果缓存中有，直接返回即可
        Map<String, String> lcsMap = new HashMap<>();
        long start = System.currentTimeMillis();
        String res = lcs(str1, str2, lcsMap);
        long end = System.currentTimeMillis();
        System.out.println("res："+res);
        System.out.println("执行时间：" + (end - start));
    }

    /**
     * 递归计算两个序列的最长公共子序列并返回结果
     * @param str1  第一个序列
     * @param str2  第二个序列
     * @return  res
     */
    private String lcs(String str1, String str2, Map<String, String> lcsMap) {
        //最后的结果存储在此局部变量内
        String lcsRes = "";

        //如果str1包含str2，直接返回str2即可
        if (str1.contains(str2)) {
            return str2;
        }
        //如果str2包含str1，直接返回str1即可
        if (str2.contains(str1)) {
            return str1;
        }

        //边界判断，如果没有数据直接返回结果即可
        if (str1.length() <= 0 || str2.length() <= 0) {
            return lcsRes;
        }

        String strKey = str1 + "_" + str2;

        //查询缓存中是否存在该key，有就return
        if (lcsMap.containsKey(strKey)) {
            return lcsMap.get(strKey);
        }

        //截取最后一位字符
        String str1Last = str1.substring(str1.length()-1);
        String str2Last = str2.substring(str2.length()-1);

        //截取除了最后一位字符后剩余的字符
        String str1Content = str1.substring(0, str1.length()-1);
        String str2Content = str2.substring(0, str2.length()-1);

        //判断第一位字符是否相同，忽略大小写判断
        if (str1Last.equalsIgnoreCase(str2Last)) {
            lcsRes = lcs(str1Content, str2Content, lcsMap) + str1Last;
        } else {
            //比较剩余的内容并存储
            String strRes1 = lcs(str1Content, str2, lcsMap);
            String strRes2 = lcs(str2Content, str1, lcsMap);

            if (strRes1.length() > strRes2.length()) {
                lcsRes = strRes1;
            } else {
                lcsRes = strRes2;
            }
        }

        //存入每次计算的结果，来减少内存消耗，提升性能
        if (!lcsMap.containsKey(strKey)) {
            lcsMap.put(strKey, lcsRes);
        }

        return lcsRes;
    }

}