wordpress纯静态网站,企业网站后台管理系统模板,网站 怎么做百度才能搜索出来,如何制作公司网站免费1. 题目
1035. 不相交的线
2. 解题思路
题目一看是求最值#xff0c;那就可以考虑用DP来做。 核心点就是确定DP数组的含义以及状态转移方程#xff1a;
dp数组含义#xff1a;dp[i][j]#xff0c;nums1 前 i 个数和 nums2 前 j 个数的最大连线数dp[i][j] dp[i - 1][j …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];}
}
