公司网站建设好宝安网站建设

动态规划算法10

LeetCode 300 最长递增子序列 2023.12.15

• 题目链接
• 代码随想录讲解[链接]
  

int lengthOfLIS(vector<int>& nums) {//创建变量result存储最终答案,设默认值为1int result = 1;//1确定dp数组，dp[i]表示以nums[i]为结尾的子数组的最长长度vector<int> dp(nums.size(), 1);//3初始化，所有元素默认的长度都为1，在创建时均已初始化//2确定递推公式，4确定遍历顺序//递推公式dp[i]表示以nums[i]为结尾的最长长度=max(以比nums[i]小的值结尾的最长长度+1(nums[i])，dp[i])//先正序遍历nums数组，然后可以正序或倒序遍历(0, i)更新dp[i]for (int i = 1; i < nums.size(); i++){for (int j = 0; j < i; j++){if(nums[j] < nums[i])dp[i] = max(dp[j] + 1, dp[i]);}//更新result值，为当前数组的递增序列最长长度if(result < dp[i])result = dp[i];}return result;
}

LeetCode 674 最长连续递增序列 2023.12.15

• 题目链接
• 代码随想录讲解[链接]
  

int findLengthOfLCIS(vector<int>& nums) {//创建变量result存储最终答案,设默认值为1int result = 1;//1确定dp数组，dp[i]表示以nums[i]为结尾的连续递增子数组的最长长度vector<int> dp(nums.size(), 1);//3初始化，所有元素默认的长度都为1，在创建时均已初始化//2确定递推公式，4确定遍历顺序//递推公式dp[i]表示：如果nums[i-1]<nums[i]，//那么以nums[i]为结尾的连续递增子数组最长长度=dp[i-1]+1for (int i = 1; i < nums.size(); i++){if(nums[i] > nums[i-1])dp[i] = dp[i-1] + 1;//更新result值，为当前数组的递增序列最长长度if(result < dp[i])result = dp[i];}return result;
}

LeetCode 718 最长重复子数组 2023.12.15

• 题目链接
• 代码随想录讲解[链接]
  

int findLength(vector<int>& nums1, vector<int>& nums2) {//创建变量result存储最终答案,设默认值为1int result = 0;//1确定dp二维数组，dp[i][j]表示以nums1[i-1]、nums2[j-1]结尾的相同子数组的最大长度vector<vector<int>> dp(nums1.size()+1, vector<int>(nums2.size()+1, 0));//3初始化，第一行和第一列必须初始化，意义上为0//2确定递推公式，4确定遍历顺序//如果nums1[i-1]、nums2[j-1]相同,那么dp[i][j]+1//顺序遍历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;//更新相同数组长度最大值if(result < dp[i][j])result = dp[i][j];}}return result;
}