177、【动态规划】leetcode ——11035. 不相交的线(C++版本)
2023-09-11 14:20:01 时间
题目描述
原题链接:1035. 不相交的线
解题思路
问题转化:如果想要不相交的连接两两相同的数字,那么就要求按从左到右的顺序,递增找公共子序列。这样子问题就转化为了找到两个最长公共子序列。解题思路与
1143. 最长公共子序列 相同
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int n1 = nums1.size(), n2 = nums2.size();
vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1));
for(int i = 1; i <= n1; i++) {
for(int j = 1; j <= n2; 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[n1][n2];
}
};
相关文章
- C++编程技巧(长期更新)
- 深入理解C/C++ [Deep C (and C++)] (2)
- [h5棋牌项目]-10-c++ 如何把一个数组的值赋到另一个数组
- 【华为OD机试 2023最新 】 九宫格(C++)
- 解答私信@被c++折磨头秃的花季美少女 //C++ 编写一个进阶版的进制转换程序,运行功能如下:请选择要输入的数字的进制(2、8、10、16):请输入该数字:请选择要转换成的进制(2、8。。。
- LeetCode 4. 寻找两个正序数组的中位数(执行用时: 20 ms , 在所有 C++ 提交中击败了 94.05% 的用户)
- LeetCode 整数转罗马数字(执行用时: 12 ms , 在所有 C++ 提交中击败了 32.38% 的用户)
- Leetcode 两数之和 C / C++
- C++ 数组中出现次数超过一半的数字
- [LeetCode] 032. Longest Valid Parentheses (Hard) (C++)
- c++ 智能指针 传参
- 【Mac系统】Vscode使用LeetCode插件报错‘leetcode.toggleLeetCodeCn‘ not found
- 【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
- 图书管理系统(C++)