給定兩個整數陣列
nums1和nums2，可以在相等的元素間畫連線，但連線不能交叉。求最多能畫幾條不交叉的連線。
Example:
Input: nums1 = [1,4,2], nums2 = [1,2,4] Output: 2
Intuition
TIP
不交叉的連線等同於兩個陣列的最長公共子序列（LCS）。
- 連線不交叉 = 匹配的元素保持相對順序 = LCS 問題
dp[i][j]=nums1[0..i-1]和nums2[0..j-1]的 LCS 長度- 若
nums1[i-1] == nums2[j-1]：dp[i][j] = dp[i-1][j-1] + 1 - 否則：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Approaches
1. Standard 2D DP — O(m * n) / O(m * n)
- Idea: 經典 LCS 二維 DP
- Time:
O(m * n) - Space:
O(m * n)
class Solution {
fun maxUncrossedLines(nums1: IntArray, nums2: IntArray): Int {
val m = nums1.size
val n = nums2.size
val dp = Array(m + 1) { IntArray(n + 1) }
for (i in 1..m) {
for (j in 1..n) {
dp[i][j] = if (nums1[i - 1] == nums2[j - 1]) {
dp[i - 1][j - 1] + 1
} else {
maxOf(dp[i - 1][j], dp[i][j - 1])
}
}
}
return dp[m][n]
}
}⭐ 2. Space-Optimized 1D DP — O(m * n) / O(min(m, n))
- Idea: 只用一維陣列 + prev 變數，將空間降至 O(min(m,n))
- Time:
O(m * n) - Space:
O(min(m, n))
class Solution {
fun maxUncrossedLines(nums1: IntArray, nums2: IntArray): Int {
// 確保 nums2 是較短的，以節省空間
val a = if (nums1.size >= nums2.size) nums1 else nums2
val b = if (nums1.size >= nums2.size) nums2 else nums1
val m = a.size; val n = b.size
val dp = IntArray(n + 1)
for (i in 1..m) {
var prev = 0
for (j in 1..n) {
val temp = dp[j]
dp[j] = if (a[i - 1] == b[j - 1]) {
prev + 1
} else {
maxOf(dp[j], dp[j - 1])
}
prev = temp
}
}
return dp[n]
}
}🔑 Takeaways
- Pattern: LCS（最長公共子序列）— 問題的幾何描述可以轉化為序列匹配問題
- Key trick: 認出「不交叉連線」等同於 LCS 是解題關鍵；空間優化時需要用
prev變數保存左上角的值