[Mdp] lc1035. 不相交的線(LCS+最長公共子序列+線性dp)

文章目錄

• • 1. 題目來源
  • 2. 題目解析

1. 題目來源

連結：1035. 不相交的線

相關題目：[線性dp] 最長公共子序列(模闆題+最長公共子序列模型)

2. 題目解析

很明顯問題可以轉化為

LCS

，問題。且資料範圍很小，元素也可以重複出現，故不能轉化為

LIS

問題。就用樸素的雙重循環解決即可。和

LCS

一模一樣。

時間複雜度： O ( n 2 ) O(n^2) O(n2)

空間複雜度： O ( n 2 ) O(n^2) O(n2)

代碼：

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1));
        
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ ) {
                if (nums1[i - 1] == nums2[j - 1]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
                else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            }
        return f[n][m];
    }
};