📢📢📢📣📣📣

哈喽！大家好，我是【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;    }}

♻️执行效果

✅递归+动态规划的优点

我们可以看到， 使用递归+动态规划，从原来的16s到现在的2ms， 可以说是大大的提高了性能，增强了系统的可用性与健壮性！

♨️往期精彩热文回顾

✈️ 3分钟带你搞懂Vue双向绑定原理及问题剖析

✈️ Netty进阶 – WebSocket长连接开发

✈️ Netty进阶 – 非阻塞网络编程 实现群聊+私聊+心跳检测系统

✈️ Postman测试工具调试接口详细教程【向后端发送Json数据并接收返回的Json结果】

✈️ Java面向对象 — 吃货联盟订餐系统（完整版）

✈️ 一分钟教你快速 搭建Vue脚手架（Vue-Cli）项目并整合ElementUI

⛵小结

以上就是【Bug 终结者】对 动态规划之两个字符串的最长公共子序列简单的概述，动态规划可以说是各个大厂的高频面试题，所以说，必须掌握，合理的使用 动态规划可以大大的提升系统的性能 ！

如果这篇【文章】有帮助到你，希望可以给【Bug 终结者】点个赞👍，创作不易，如果有对【后端技术】、【前端领域】感兴趣的小可爱，也欢迎关注❤️❤️❤️ 【Bug 终结者】❤️❤️❤️，我将会给你带来巨大的【收获与惊喜】💝💝💝！