app开发导入网站模板,个人网站建设怎么赚钱,wordpress友链页面,图片网站的优化目录 1143.最长公共子序列 1035.不相交的线 53. 最大子序和 动态规划 1143.最长公共子序列 题目链接#xff1a;1143. 最长公共子序列 #xff08;1#xff09;dp[ i ][ j ] 表示 text1 前 i 个元素、text2 前 j 个元素的最长公共子序列的长度#xff1b; #xff08;21143. 最长公共子序列 1dp[ i ][ j ] 表示 text1 前 i 个元素、text2 前 j 个元素的最长公共子序列的长度 2if( text1[ i - 1 ] text2[ j - 1 ] ) dp[ i ][ j ] dp[ i - 1 ][ j - 1 ] 1; else dp[ i ][ j ] dp[ i - 1 ][ j - 1 ]; 3dp[ 0 ][ 0 ]设为空状态dp[ i ][ j ] 0; 4外层遍历 text1内层遍历 text2 class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vectorvectorint dp(text1.size() 1, vectorint(text2.size() 1, 0));for(int i 1; i text1.size(); i){for(int j 1; j text2.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 - 1][j], dp[i][j - 1]);}}return dp[text1.size()][text2.size()];}
}; 1035.不相交的线 题目链接1035. 不相交的线 被题目复杂的表面吓到了。 实际上上一题中的公共子序列得到的两个字符串中相对位置是有顺序的所有按照公共子序列进行连线并不会相交所以本题实质上和上一题是一模一样的只需要改变量名即可。 class Solution {
public:int maxUncrossedLines(vectorint nums1, vectorint nums2) {vectorvectorint dp(nums1.size() 1, vectorint(nums2.size() 1, 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 - 1][j], dp[i][j - 1]);}}return dp[nums1.size()][nums2.size()];}
}; 53. 最大子序和 动态规划 题目链接53. 最大子数组和 之前用贪心算法做过动态规划的思路也差不多 1dp[ i ] 表示以第 i 个元素结尾的数组的和 2dp[ i ] max( dp[ i - 1 ] nums[ i ], nums[ i ] ); if ( dp[ i ] ans ) ans dp[ i ]; 3dp[ 0 ] nums[ 0 ]; 4遍历 nums 数组 class Solution {
public:int maxSubArray(vectorint nums) {vectorint dp(nums.size(), 0);int ans nums[0];dp[0] max(nums[0], 0);for(int i 1; i nums.size(); i){dp[i] max(dp[i - 1] nums[i], nums[i]);if(dp[i] ans) ans dp[i];}return ans;}
};
