解題說明
C++ 解法
複雜度分析
虛擬碼
1. Initialize dp[m+1][n+1] with zeros.
2. For i from 1 to m:
For j from 1 to n:
a. If nums1[i-1] == nums2[j-1]: dp[i][j] = dp[i-1][j-1] + 1.
b. Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
3. Return dp[m][n].1. Initialize dp[m+1][n+1] with zeros.
2. For i from 1 to m:
For j from 1 to n:
a. If nums1[i-1] == nums2[j-1]: dp[i][j] = dp[i-1][j-1] + 1.
b. Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
3. Return dp[m][n].題目描述：
給定兩個整數陣列 nums1 和 nums2，在 nums1[i] 和 nums2[j] 之間畫線（當 nums1[i] == nums2[j] 時）。線不能交叉。求最多能畫幾條不交叉的連線。
解題思路： 此題本質上就是**最長公共子序列（LCS）**問題。
兩條線不交叉等價於：選出的配對 (i1, j1), (i2, j2), ... 滿足 i1 < i2 < ... 且 j1 < j2 < ...，這正是公共子序列的定義。
定義 dp[i][j] = nums1[0..i-1] 和 nums2[0..j-1] 的最長公共子序列長度。
轉移：
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])。時間複雜度：O(m * n) — 雙重迴圈遍歷所有 (i, j) 狀態。
空間複雜度：O(m * n) — 二維 DP 陣列。可優化為 O(min(m, n))（滾動陣列）。
滾動陣列優化：O(m * n) 時間、O(min(m, n)) 空間。由於 dp[i] 只依賴 dp[i-1]，可用一維陣列 + 一個臨時變數實現。
Hunt-Szymanski 演算法：O((r + n) log n) 時間，其中 r 是匹配對數量。當匹配對稀疏時更快。將問題轉化為最長遞增子序列（LIS），適用於大規模稀疏輸入。