📢📢📢📣📣📣
哈喽！大家好，我是【Bug 终结者】 ，【CSDN新星创作者】🏆，阿里云技术博主🏆，51CTO人气博主🏆，INfoQ写作专家🏆
一位上进心十足，拥有极强学习力的【Java领域博主】😜😜😜
🏅【Bug 终结者】博客的领域是【面向后端技术】的学习，未来会持续更新更多的【后端技术】以及【学习心得】。 偶尔会分享些前端基础知识，会更新实战项目，面向企业级开发应用！
🏅 如果有对【后端技术】、【前端领域】感兴趣的【小可爱】，欢迎关注【Bug 终结者】💞💞💞
❤️❤️❤️ 感谢各位大可爱小可爱！ ❤️❤️❤️
@[TOC]
一、什么是动态规划？
动态规划（英语：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， 可以说是大大的提高了性能，增强了系统的可用性与健壮性！
♨️往期精彩热文回顾
✈️ Netty进阶 -- WebSocket长连接开发
✈️ Netty进阶 -- 非阻塞网络编程 实现群聊+私聊+心跳检测系统 **
✈️ 一分钟教你快速 搭建Vue脚手架（Vue-Cli）项目并整合ElementUI
⛵小结
以上就是【Bug 终结者】对 动态规划之两个字符串的最长公共子序列简单的概述，动态规划可以说是各个大厂的高频面试题，所以说，必须掌握，合理的使用 动态规划可以大大的提升系统的性能 ！
如果这篇【文章】有帮助到你，希望可以给【Bug 终结者】点个赞👍，创作不易，如果有对【后端技术】、【前端领域】感兴趣的小可爱，也欢迎关注❤️❤️❤️ 【Bug 终结者】❤️❤️❤️，我将会给你带来巨大的【收获与惊喜】💝💝💝！
