新闻网站内容建设措施上海网站建设联系方式

1. 题目

1035. 不相交的线

2. 解题思路

题目一看是求最值，那就可以考虑用DP来做。
核心点就是确定DP数组的含义以及状态转移方程：

• dp数组含义：dp[i][j]，nums1 前 i 个数和 nums2 前 j 个数的最大连线数
• dp[i][j] = dp[i - 1][j - 1] + 1;可以在这两个元素之间画一条线，所以当前的最大线数等于 dp[i-1][j-1] + 1。即在之前的最优解上多加一条新线。
• 无法直接连接当前元素，当前状态的最大线数应该是从前面的状态转移过来，选择 dp[i-1][j] 或 dp[i][j-1] 中较大的那个值（即两个数组中前面的最优解）。

3. 代码

3.1. 注意事项

[!NOTE] 1、DP数组的大小
因为DP的含义是前N个数，所以前0个数相当于没有啥用，所以要获取到最后题目要求的结果那就是要dp[m][n] ，所以初始化大小要初始化为int[m + 1][n + 1]

[!NOTE] 2、for循环边界
还是根据DP数组的含义，需要到达m和n，所以for循环需要能够等于数组长度

[!NOTE] 3、为什么for循环里面用nums1[i - 1] == nums2[j - 1] 而不用nums[i]来判断
因为动态规划数组 f[i][j] 的下标从 1 开始，而 nums1 和 nums2 的数组下标是从 0 开始的。通过使用 i-1 和 j-1 来索引 nums1 和 nums2，可以正确对齐两个数组的元素与动态规划表的状态。

3.2. 完整代码

class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int m = nums1.length;int n = nums2.length;if (m == 0 || n == 0) {return 0;}//dp数组含义：dp[i][j]，nums1 前 i 个数和 nums2 前 j 个数的最大连线数int[][] dp = new int[m + 1][n + 1];//初始化base case 默认dp[0][0]为0，即前0个数的最大连线数是0for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[m][n];}
}