Day47 | 动态规划 ：线性DP 最长公共子序列&&最长公共子数组

Day47 | 动态规划 ：线性DP 最长公共子序列&&最长公共子数组

动态规划应该怎样学习？-CSDN博客
本次题解参考自灵神的做法，各人也多多支持灵神的题解
最长公共子序列 编辑间隔_哔哩哔哩_bilibili
动态规划学习：
1.思索回溯法（深度优先遍历）怎么写
注意要画树形结构图
2.转成影象化搜索
看哪些地方是重复盘算的，怎么用影象化搜索给顶替掉这些重复盘算
3.把影象化搜索翻译成动态规划
根本就是1:1转换


1143.最长公共子序列

[1143. 最长公共子序列 - 力扣（LeetCode）](https://leetcode.cn/problems/longest-increasing-subsequence/description/)
思绪分析（子题目）:

设两个字符串分别是s和t
对应的末了一个字母分别是x和y
dfs(x,y)那就是s以x末端，t以y末端的两个字符串的最长公共子序列的长度了
那就有四种环境
1.选x这个字母也选y这个字母
2.不选x不选y
3.选x不选y
4.选y不选x
假如x==y，那肯定就是选x也选y，那肯定就是

1. dfs(x,y)=dfs(x-1,y-1)+1

复制代码

假如说x!=y，那么就是剩下三种环境内里取一个最大值

1. dfs(x,y)=max(dfs(x-1,y-1),dfs(x,y-1),dfs(x-1,y))

复制代码

再过细一看，实在
dfs(x,y-1),dfs(x-1,y)包罗了dfs(x-1,y-1)，以是不须要这个了

1. dfs(x,y)=max(dfs(x,y-1),dfs(x-1,y))

复制代码

不明白可以举例

1. dfs(x,y-1)=max(dfs(x-1,y-1),dfs(x,y-2))

复制代码

递归边界：
只要x大概y小于0，那么就分析有一个字符串已经没有字母可以选择了，那么就到达了边界。
1.回溯 DFS

1.返回值和参数
i是上面x字母的下标，j是y的下标
dfs(i,j)那就是s以x末端，t以y末端的两个字符串的最长公共子序列的长度了

1. int dfs(int i,int j,string &s,string &t)

复制代码

2.停止条件
只要有一个小于0就分析没有字符可以选了

1. if(i<0||j<0)
2.         return 0;

复制代码

3.本层逻辑
相称就+1，不相称就三种选一种

1.                 if(s[i]==t[j])
2.             return dfs(i-1,j-1,s,t)+1;
3.         else
4.             return max(dfs(i-1,j,s,t),dfs(i,j-1,s,t));

复制代码

完备代码：
固然，这是超时的

1. class Solution {public:    int dfs(int i,int j,string &s,string &t)
2.     {        if(i<0||j<0)            return 0;        if(s[i]==t[j])            return dfs(i-1,j-1,s,t)+1;        else            return max(dfs(i-1,j,s,t),dfs(i,j-1,s,t));    }    int longestCommonSubsequence(string text1, string text2) {        return dfs(text1.size()-1,text2.size()-1,text1,text2);    }};

复制代码

1. //lambda
2. class Solution {
3. public:
4.     int longestCommonSubsequence(string text1, string text2) {
5.         function<int(int,int)> dfs=[&](int i,int j)->int{
6.             if(i<0||j<0)
7.             return 0;
8.             if(text1[i]==text2[j])
9.                 return dfs(i-1,j-1)+1;
10.             else
11.                 return max(dfs(i-1,j),dfs(i,j-1));
12.         };
13.         return dfs(text1.size()-1,text2.size()-1);
14.     }
15. };

复制代码

2.影象化搜索

就是搞一个哈希表dp，全都初始化为-1，每次返回前给哈希表dp赋值，遇到不是-1的那就是算过的，那就直接返回盘算过的结果，不须要再次递归了

1. class Solution {
2. public:
3.     int dfs(int i,int j,string &s,string &t,vector<vector<int>> &dp)
4.     {
5.         if(i<0||j<0)
6.             return 0;
7.         if(dp[i][j]!=-1)
8.             return dp[i][j];
9.         if(s[i]==t[j])
10.             return dp[i][j]=dfs(i-1,j-1,s,t,dp)+1;
11.         else
12.             return dp[i][j]=max(dfs(i-1,j,s,t,dp),dfs(i,j-1,s,t,dp));
13.     }
14.     int longestCommonSubsequence(string text1, string text2) {
15.         vector<vector<int>> dp(text1.size(),vector<int>(text2.size(),-1));
16.         return dfs(text1.size()-1,text2.size()-1,text1,text2,dp);
17.     }
18. };

复制代码

1. //lambda
2. class Solution {
3. public:
4.     int longestCommonSubsequence(string text1, string text2) {
5.         vector<vector<int>> dp(text1.size(),vector<int>(text2.size(),-1));
6.         function<int(int,int)> dfs=[&](int i,int j)->int{
7.             if(i<0||j<0)
8.                 return 0;
9.             if(dp[i][j]!=-1)
10.                 return dp[i][j];
11.             if(text1[i]==text2[j])
12.                 return dp[i][j]=dfs(i-1,j-1)+1;
13.             else
14.                 return dp[i][j]=max(dfs(i-1,j),dfs(i,j-1));
15.         };
16.         return dfs(text1.size()-1,text2.size()-1);
17.     }
18. };

复制代码

3.1:1翻译为动态规划

1.确定dp数组以及下标的寄义
dp[j]就是dfs(I,j)
下标从1开始，下标0纪录的是上面if停止条件内里的(i<0||j<0)的非法状态
2.确定递推公式
和dfs中也是对应的

1.                                 if(text1[i]==text2[j])
2.                     dp[i+1][j+1]=dp[i][j]+1;
3.                 else
4.                     dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);

复制代码

3.dp数组怎样初始化
都初始化为0即可

1. vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));

复制代码

4.确定遍历次序
从前往后遍历即可

1.                 for(int i=0;i<text1.size();i++)
2.             for(int j=0;j<text2.size();j++)
3.                 if(text1[i]==text2[j])
4.                     dp[i+1][j+1]=dp[i][j]+1;
5.                 else
6.                     dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
7.         return dp[text1.size()][text2.size()];

复制代码

完备代码

1. class Solution {public:    int longestCommonSubsequence(string text1, string text2) {        vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));
2.         for(int i=0;i<text1.size();i++)            for(int j=0;j<text2.size();j++)                if(text1[i]==text2[j])                    dp[i+1][j+1]=dp[i][j]+1;                else                    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);        return dp[text1.size()][text2.size()];    }};

复制代码

718.最长重复子数组

718. 最长重复子数组 - 力扣（LeetCode）
思绪：

实在就是最长一连公共子序列，在上一题条件中加了一个一连
递归公式就变成了

1. if(nums1[i]==nums2[j])
2.         dp[i+1][j+1]=dp[i][j]+1;

复制代码

由于要求的是一连，以是只要x和y不相称，那就直接是0
注意一个区别就是这里须要一个变量纪录一下最大值，剩下的都一样了
动态规划

1. class Solution {
2. public:
3.     int findLength(vector<int>& nums1, vector<int>& nums2) {
4.         vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
5.         int res=0;
6.         for(int i=0;i<nums1.size();i++)
7.             for(int j=0;j<nums2.size();j++)
8.             {
9.                 if(nums1[i]==nums2[j])
10.                     dp[i+1][j+1]=dp[i][j]+1;
11.                 res=max(res,dp[i+1][j+1]);
12.             }
13.         return res;   
14.     }
15. };

复制代码

1035.不相交的线

1035. 不相交的线 - 力扣（LeetCode）
和上面最长公共子序列一个意思，代码就只是把s换成nums1，把t换成nums2，仅此而已
动态规划

1. class Solution {
2. public:
3.     int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
4.         vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
5.         for(int i=0;i<nums1.size();i++)
6.             for(int j=0;j<nums2.size();j++)
7.                 if(nums1[i]==nums2[j])
8.                     dp[i+1][j+1]=dp[i][j]+1;
9.                 else
10.                     dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
11.         return dp[nums1.size()][nums2.size()];
12.     }
13. };

复制代码