2024-12-11 21:31 门头沟学院 C++ 发布于江西
关注
day43
今天完成了三道动规的子序列题，有点难度。
最长递增子序列：
//dp[i]：下标为i时的最长递增子序列的长度
//递推公式：
//if(nums[i] > nums[j]) dp[i] = max(dp[j] + 1, dp[i]);
//初始化：全初始化为1
//遍历顺序，两层for循环，外层i，内层j（j < i）
if(nums.size() == 0) return 0;
vector dp(nums.size(), 1);
int result = 1;
for(int i = 1; i < nums.size(); i++)
{
for(int j = 0; j < i; j++)
{
if(nums[i] > nums[j]){
dp[i] = max(dp[j] + 1, dp[i]);
}
}
result = max(result, dp[i]);
}
return result;//不一定是以最后一个元素为结尾时是最长子序列
最长连续递增子序列：简单
两个数组间的最长重复数组：
//dp[i][j]：以i-1为结尾的A和以j-1为结尾的B的最长重复子数组的长度
//注意： “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串
//递推公式：
//if(nums[i] == nums[j]) dp[i][j] = dp[i-1][j-1] + 1;
//初始化，全初始化为0，因为dp[i][0],dp[0][j]其实没有意义，而其他的则会被覆盖
//遍历顺序：两层for循环
if(nums1.size() == 0 || nums2.size() == 0) return 0;
vector> dp(nums1.size() + 1, vector(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])//是i-1，j-1时的元素相等
{
dp[i][j] = dp[i-1][j-1] + 1;
}
result = max(dp[i][j], result);//持续记录最大值
}
}
return result;
这几天终于把Reactor框架学完了！
最长递增子序列：
//dp[i]：下标为i时的最长递增子序列的长度
//递推公式：
//if(nums[i] > nums[j]) dp[i] = max(dp[j] + 1, dp[i]);
//初始化：全初始化为1
//遍历顺序，两层for循环，外层i，内层j（j < i）
if(nums.size() == 0) return 0;
vector
int result = 1;
for(int i = 1; i < nums.size(); i++)
{
for(int j = 0; j < i; j++)
{
if(nums[i] > nums[j]){
dp[i] = max(dp[j] + 1, dp[i]);
}
}
result = max(result, dp[i]);
}
return result;//不一定是以最后一个元素为结尾时是最长子序列
最长连续递增子序列：简单
两个数组间的最长重复数组：
//dp[i][j]：以i-1为结尾的A和以j-1为结尾的B的最长重复子数组的长度
//注意： “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串
//递推公式：
//if(nums[i] == nums[j]) dp[i][j] = dp[i-1][j-1] + 1;
//初始化，全初始化为0，因为dp[i][0],dp[0][j]其实没有意义，而其他的则会被覆盖
//遍历顺序：两层for循环
if(nums1.size() == 0 || nums2.size() == 0) return 0;
vector
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])//是i-1，j-1时的元素相等
{
dp[i][j] = dp[i-1][j-1] + 1;
}
result = max(dp[i][j], result);//持续记录最大值
}
}
return result;
这几天终于把Reactor框架学完了！
全部评论
相关推荐
点赞 评论 收藏
分享