当前位置 博文首页 > 数据结构和算法：LeetCode 1035. 不相交的线
截止到目前我已经写了 500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
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]);
来看下最终代码
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
//这里为了方便计算，减少一些边界条件的判断，把dp的宽高都增加1
int dp[][] = new int[m + 1][n+1];
for (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][j - 1], dp[i - 1][j]);
return dp[m][n];
}
来看下代码。
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
int dp[] = new int[n + 1];
for (int i = 1; i <= m; ++i) {
int last = dp[0];
for (int j = 1; j <= n; ++j) {
//dp[j]计算过会被覆盖，这里先把他存储起来
int temp = dp[j];
//下面是递推公式
if (nums1[i - 1] == nums2[j - 1])
dp[j] = last + 1;
else
dp[j] = Math.max(dp[j - 1], dp[j]);
last = temp;
}
}
return dp[n];
}
