当前位置: 首页> 游戏> 攻略 > 高档餐厅包房装修效果图_2021室内设计公司排名_今日新闻_服装品牌策划方案

高档餐厅包房装修效果图_2021室内设计公司排名_今日新闻_服装品牌策划方案

时间:2025/7/11 8:42:06来源:https://blog.csdn.net/jingjingjing1111/article/details/146261011 浏览次数:1次
高档餐厅包房装修效果图_2021室内设计公司排名_今日新闻_服装品牌策划方案

思路:代码随想录

1143.最长公共子序列

力扣题目链接

思路:对于要求连续的,不相等就跳过去了,但是对于不要求连续的,不相等时对上一状态要有一个继承,后面能相等的话好续上,那这样写出来的话dp[i][j]虽然定义为nums1中0~(i-1)和nums2中0~(j-1)的公共子序列,但是公共子序列的结尾不一定是在i-1或j-1

// 定义:dp[i][j]的定义为,字符串s从0到i-1和字符串t从0到j-1的相同子序列的长度
class Solution {
public:bool isSubsequence(string s, string t) {vector<vector<int>> dp(s.size()+1,vector<int>(t.size()+1,0));for(int i=1;i<=s.size();i++){for(int j=1;j<=t.size();j++){if(s[i-1]==t[j-1]) dp[i][j] = dp[i-1][j-1]+1;else dp[i][j] = dp[i][j-1];}}if(dp[s.size()][t.size()]==s.size()) return true;return false;}
};

1035.不相交的线

力扣题目链接

思路:跟上一题是一个意思,不过有一个小细节就是交叉问题,但其实这样顺着记录不会交叉,举一个简单的例子1,2和2,1模拟一下就可以了

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

53. 最大子序和

力扣题目链接

思路:和贪心思路类似,贪心是显性地用0来判断取舍,动规的判断位置相对贪心往后移了一位,直接以数值和来判断

定义:dp[i]表示前nums[i](含)之前的子序列的最大和

递推公式:dp[i]取算上前面的序列和 与 从不加前面的从当前开始计算的值 之间的最大值,定义一个result不断记录最大值,有点像贪心

初始化:第一个初始化为第一个数字

遍历顺序:从前向后

class Solution {
public:int maxSubArray(vector<int>& nums) {int result = nums[0];vector<int> dp(nums.size());dp[0]=nums[0];for(int i=1;i<nums.size();i++){dp[i]=max(dp[i-1]+nums[i],nums[i]);if(dp[i]>result) result=dp[i];}return result;}
};

 

392.判断子序列

力扣题目链接

思路:和前面求 1143.最长公共子序列思路大致一致

区别在递推公式处,是删掉第二个数组中的数字去碰第一个数组,所以遍历到两个数字不相等的时候,不是比较dp[i][j-1]和dp[i-1][j],而是忽略掉当前的第二个数组的j-1处,直接等于从j-2处继承过来的值

// 定义:dp[i][j]的定义为,字符串s从0到i-1和字符串t从0到j-1的相同子序列的长度
class Solution {
public:bool isSubsequence(string s, string t) {vector<vector<int>> dp(s.size()+1,vector<int>(t.size()+1,0));for(int i=1;i<=s.size();i++){for(int j=1;j<=t.size();j++){if(s[i-1]==t[j-1]) dp[i][j] = dp[i-1][j-1]+1;else dp[i][j] = dp[i][j-1];}}if(dp[s.size()][t.size()]==s.size()) return true;return false;}
};
关键字:高档餐厅包房装修效果图_2021室内设计公司排名_今日新闻_服装品牌策划方案

版权声明:

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

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

责任编辑: