青岛网站制作服务,装饰设计素描,会展相关网站建设情况,网络公司注册资金最低标准代码随想录算法训练营Day53 | 1143.最长公共子序列 1035.不相交的线 53. 最大子序和 动态规划
LeetCode 1143.最长公共子序列
题目链接#xff1a;LeetCode 1143.最长公共子序列
思路#xff1a; 三种情况得到dp[i][j]
class Solution {
public:int longestCommonSubseq…代码随想录算法训练营Day53 | 1143.最长公共子序列 1035.不相交的线 53. 最大子序和 动态规划
LeetCode 1143.最长公共子序列
题目链接LeetCode 1143.最长公共子序列
思路 三种情况得到dp[i][j]
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m text1.size();int n text2.size();vectorvectorint dp(m1, vectorint(n1));for(int i1; im; i){for(int j1; jn; j){if(text1[i-1] text2[j-1]) dp[i][j] dp[i-1][j-1] 1;else dp[i][j] max(dp[i-1][j], dp[i][j-1]);}}return dp[m][n];}
};注意
连续判断i-1和j-1
LeetCode 1035.不相交的线
题目链接LeetCode 1035.不相交的线
思路 与上面等价
class Solution {
public:int maxUncrossedLines(vectorint nums1, vectorint nums2) {int m nums1.size();int n nums2.size();vectorvectorint dp(m1, vectorint(n1));for(int i1; im; i){for(int j1; jn; 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]);}}return dp[m][n];}
};LeetCode 53. 最大子序和 动态规划
题目链接LeetCode 53. 最大子序和 动态规划
思路 取极大值
class Solution {
public:int maxSubArray(vectorint nums) {int n nums.size();vectorint dp(n);dp[0] nums[0];int result dp[0];for(int i1; in; i){dp[i] max(dp[i-1]nums[i], nums[i]);result max(result, dp[i]);}return result;}
};注意
注意初始化dp[0] nums[0]
