1035. 不相交的线
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];}
}