您的位置:首页 > 财经 > 金融 > wap页面是什么_开个小公司需要什么条件_网站seo优化心得_合肥网站推广助理

wap页面是什么_开个小公司需要什么条件_网站seo优化心得_合肥网站推广助理

2024/12/23 10:09:00 来源:https://blog.csdn.net/m0_74795952/article/details/144041913  浏览:    关键词:wap页面是什么_开个小公司需要什么条件_网站seo优化心得_合肥网站推广助理
wap页面是什么_开个小公司需要什么条件_网站seo优化心得_合肥网站推广助理

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

动态规划应该如何学习?-CSDN博客

本次题解参考自灵神的做法,大家也多多支持灵神的题解

最长公共子序列 编辑距离_哔哩哔哩_bilibili

动态规划学习:

1.思考回溯法(深度优先遍历)怎么写

注意要画树形结构图

2.转成记忆化搜索

看哪些地方是重复计算的,怎么用记忆化搜索给顶替掉这些重复计算

3.把记忆化搜索翻译成动态规划

基本就是1:1转换

文章目录

  • Day47 | 动态规划 :线性DP 最长公共子序列&&最长公共子数组
    • 1143.最长公共子序列
      • 思路分析(子问题):
      • 1.回溯 DFS
      • 2.记忆化搜索
      • 3.1:1翻译为动态规划
    • 718.最长重复子数组
      • 思路:
      • 动态规划
    • 1035.不相交的线
      • 动态规划

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,那肯定就是

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

如果说x!=y,那么就是剩下三种情况里面取一个最大值

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),所以不需要这个了

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

不明白可以举例

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结尾的两个字符串的最长公共子序列的长度了

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

2.终止条件

只要有一个小于0就说明没有字符可以选了

if(i<0||j<0)return 0;

3.本层逻辑

相等就+1,不相等就三种选一种

		if(s[i]==t[j])return dfs(i-1,j-1,s,t)+1;elsereturn max(dfs(i-1,j,s,t),dfs(i,j-1,s,t));

完整代码:

当然,这是超时的

class Solution {
public:int dfs(int i,int j,string &s,string &t){if(i<0||j<0)return 0;if(s[i]==t[j])return dfs(i-1,j-1,s,t)+1;elsereturn 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);}
};
//lambda
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {function<int(int,int)> dfs=[&](int i,int j)->int{if(i<0||j<0)return 0;if(text1[i]==text2[j])return dfs(i-1,j-1)+1;elsereturn max(dfs(i-1,j),dfs(i,j-1));};return dfs(text1.size()-1,text2.size()-1);}
};

2.记忆化搜索

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

class Solution {
public:int dfs(int i,int j,string &s,string &t,vector<vector<int>> &dp){if(i<0||j<0)return 0;if(dp[i][j]!=-1)return dp[i][j];if(s[i]==t[j])return dp[i][j]=dfs(i-1,j-1,s,t,dp)+1;elsereturn dp[i][j]=max(dfs(i-1,j,s,t,dp),dfs(i,j-1,s,t,dp));}int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size(),vector<int>(text2.size(),-1));return dfs(text1.size()-1,text2.size()-1,text1,text2,dp);}
};
//lambda
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size(),vector<int>(text2.size(),-1));function<int(int,int)> dfs=[&](int i,int j)->int{if(i<0||j<0)return 0;if(dp[i][j]!=-1)return dp[i][j];if(text1[i]==text2[j])return dp[i][j]=dfs(i-1,j-1)+1;elsereturn dp[i][j]=max(dfs(i-1,j),dfs(i,j-1));};return dfs(text1.size()-1,text2.size()-1);}
};

3.1:1翻译为动态规划

1.确定dp数组以及下标的含义

dp[i][j]就是dfs(I,j)

下标从1开始,下标0记录的是上面if终止条件里面的(i<0||j<0)的非法状态

2.确定递推公式

和dfs中也是对应的

				if(text1[i]==text2[j])dp[i+1][j+1]=dp[i][j]+1;elsedp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);

3.dp数组如何初始化

都初始化为0即可

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

4.确定遍历顺序

从前往后遍历即可

		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;elsedp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);return dp[text1.size()][text2.size()];

完整代码

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));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;elsedp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);return dp[text1.size()][text2.size()];}
};

718.最长重复子数组

718. 最长重复子数组 - 力扣(LeetCode)

思路:

其实就是最长连续公共子序列,在上一题条件中加了一个连续

递归公式就变成了

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

因为要求的是连续,所以只要x和y不相等,那就直接是0

注意一个区别就是这里需要一个变量记录一下最大值,剩下的都一样了

动态规划

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));int res=0;for(int i=0;i<nums1.size();i++)for(int j=0;j<nums2.size();j++){if(nums1[i]==nums2[j])dp[i+1][j+1]=dp[i][j]+1;res=max(res,dp[i+1][j+1]);}return res;   }
};

1035.不相交的线

1035. 不相交的线 - 力扣(LeetCode)

和上面最长公共子序列一个意思,代码就只是把s换成nums1,把t换成nums2,仅此而已

动态规划

class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));for(int i=0;i<nums1.size();i++)for(int j=0;j<nums2.size();j++)if(nums1[i]==nums2[j])dp[i+1][j+1]=dp[i][j]+1;elsedp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);return dp[nums1.size()][nums2.size()];}
};

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com