Victory belongs to those who believe in it the most and believe in it the longest.
胜利属于那些意志坚强、持之以恒的人。
问题描述
来源：LeetCode第1035题
难度：中等
在两条独立的水平线上按给定的顺序写下nums1和nums2中的整数。现在，可以绘制一些连接两个数字nums1[i]和nums2[j]的直线，这些直线需要同时满足满足：
-
nums1[i] == nums2[j]
-
且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
以这种方法绘制线条，并返回可以绘制的最大连线数。
示例 1：
输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
示例 2：
输入：nums1 = [2,5,1,2,5],
nums2 = [10,5,2,1,5,2]
输出：3
示例 3：
输入：nums1 = [1,3,7,1,7,5],
nums2 = [1,9,2,5,1]
输出：2
提示：
-
1 <= nums1.length <= 500
-
1 <= nums2.length <= 500
-
1 <= nums1[i], nums2[i] <= 2000
动态规划解决
定义dp[i][j]表示数组nums1的前i个元素和nums2的前j个元素所能绘制的最大连接数，如果要求dp[i][j]，我们首先判断nums1的第i个元素和nums2的第j个元素是否相等
如果相等，说明nums1的第i个元素可以和nums2的第j个元素可以连成一条线，这个时候nums1的前i个元素和nums2的前j个元素所能绘制的最大连接数就是nums1的前i-1个元素和nums2的前j-1个元素所能绘制的最大连接数加1，也就是dp[i][j]=dp[i-1][j-1]+1;
如果不相等，我们就把nums1去掉一个元素，计算nums1的前i-1个元素和nums2的前j个元素能绘制的最大连接数，也就是dp[i-1][j]，或者把nums2去掉一个元素，计算nums2的前j-1个元素和nums1的前i个元素能绘制的最大连接数，也就是dp[i][j-1]，这两种情况我们取最大的即可，所以我们可以找出递推公式
if(nums[i] == nums[j]) dp[i][j] = dp[i-1][j-1] + 1;else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
来看下最终代码
1public int maxUncrossedLines(int[] nums1, int[] nums2) {
2 int m = nums1.length, n = nums2.length;
3 //这里为了方便计算，减少一些边界条件的判断，把dp的宽高都增加1
4 int dp[][] = new int[m + 1][n+1];
5 for (int i = 1; i <= m; ++i)
6 for (int j = 1; j <= n; ++j)
7 //下面是递推公式
8 if (nums1[i - 1] == nums2[j - 1])
9 dp[i][j] = dp[i - 1][j - 1] + 1;
10 else
11 dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
12 return dp[m][n];
13}
动态规划代码优化
上面代码中计算当前值的时候只会和左边，上边，左上边这3个位置的值有关，和其他的值无关，所以没必要使用二维数组，我们可以改为一维数组，怎么改我们画个图看一下
如果只是
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j])，
我们直接把前面的一维去掉即可，其他的不需要修改，即
dp[j] = Math.max(dp[j - 1], dp[j]);
如下图所示，
如果
dp[i][j] = dp[i - 1][j - 1] + 1
上面方式就行不通了，如果改为
dp[j] = dp[j - 1] + 1，
我们发现这个dp[j - 1] 并不是之前的那个dp[j - 1]，在前一步计算的时候已经被覆盖掉了，所以我们需要一个变量在计算dp[j - 1]的值之前先要把dp[j - 1]的值给存起来，如下图所示
来看下代码。
1public int maxUncrossedLines(int[] nums1, int[] nums2) {
2 int m = nums1.length, n = nums2.length;
3 int dp[] = new int[n + 1];
4 for (int i = 1; i <= m; ++i) {
5 int last = dp[0];
6 for (int j = 1; j <= n; ++j) {
7 //dp[j]计算过会被覆盖，这里先把他存储起来
8 int temp = dp[j];
9 //下面是递推公式
10 if (nums1[i - 1] == nums2[j - 1])
11 dp[j] = last + 1;
12 else
13 dp[j] = Math.max(dp[j - 1], dp[j]);
14 last = temp;
15 }
16 }
17 return dp[n];
18}
总结
这题其实就是求最长公共子序列问题，只不过换了一种说法。
截止到目前我已经写了500多道算法题了，为了方便大家阅读，我把部分算法题整理成了pdf文档，目前有1000多页，大家可以在公众号中回复关键字“pdf”即可获取下载链接。