负责公司网站的更新和维护,广州网站设计公司哪里济南兴田德润怎么联系,推广比较好的网站有哪些,家装公司文案1143.最长公共子序列 题目链接 1143. 最长公共子序列 - 力扣#xff08;LeetCode#xff09; 讲解链接 代码随想录 (programmercarl.com) 给定两个数组#xff0c;求最长公共子序列#xff0c;此时dp数组需要用二维的#xff0c;dp[i][j]表示下表i-1.j-1所能拥有的最长公共… 1143.最长公共子序列 题目链接 1143. 最长公共子序列 - 力扣LeetCode 讲解链接 代码随想录 (programmercarl.com) 给定两个数组求最长公共子序列此时dp数组需要用二维的dp[i][j]表示下表i-1.j-1所能拥有的最长公共子序列长度为了方便定义故而用i-1,j-1),此时两个数组i,j元素有两种可能相等此时dp[i][j]dp[i-1][j-1]1;不相等dp[i][j]max(dp[i-1][j],dp[i][j-1])因为是所能达到的最大长度故要取两个的最大值 for(int i1;itext1.size();i){for(int j1;jtext2.size();j){if(text1[i-1]text2[j-1]){dp[i][j]dp[i-1][j-1]1;}else{dp[i][j]max(dp[i][j-1],dp[i-1][j]);}}} 1035.不相交的线 题目链接 1035. 不相交的线 - 力扣LeetCode 讲解链接 代码随想录 (programmercarl.com) 题目描述虽然不同但是本质却是一样的找出按数序排列的相同子序列并返回所能达到的最大值故而只需要把代码字符串换成数组即可 vectorvectorintdp(nums1.size()1,vectorint(nums2.size()1,0));for(int i1;inums1.size();i){for(int j1;jnums2.size();j){ 53. 最大子序和 题目链接 53. 最大子数组和 - 力扣LeetCode 讲解链接 代码随想录 (programmercarl.com) 动态规划五部曲
首先定义dp数组含义dp[i]表示以下标i结尾的额最大子序列和
其次,dp数组初始化dp[0]nums[0];
递归函数dp[i]有两种来由1、当前数字作为结尾续上此时dp[i]dp[i-1]nums[i], 2、从当前数字从新开始dp[i]nums[i];
递归方向从头到尾 vectorintdp(nums.size(),0);dp[0]nums[0];int resultnums[0];for(int i1;inums.size();i){dp[i]max(dp[i-1]nums[i],nums[i]);if(dp[i]result)resultdp[i];}return result;
每次将最大的和存入结果中。
