[Mdp] lc1035. 不相交的線(LCS+LIS+重點知識了解)

文章目錄

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

1. 題目來源

連結：1035. 不相交的線

相關：

• 不太相關：[線性dp] aw1012. 友好城市(最長上升子序列模型+思維)
• 強相關：[線性dp] aw897. 最長公共子序列(重要模闆題+最長公共子序列模型)
• 弱相關：[線性dp] aw895最長上升子序列(知識了解+重要模闆題+最長上升子序列模型+LCS轉化LIS)

力贊題解，知識總結，對比 LCS 與 LIS 特性，深挖 LCS 狀态分類，三葉姐yyds：

• 【宮水三葉の相信科學系列】求「最值問題」隻需要確定「不漏」即可

2. 題目解析

很有意思的一道題，不虧是小馬AI，題單裡的，哈哈。

一開始以為是做過的一道 思維+LIS，[線性dp] aw1012. 友好城市(最長上升子序列模型+思維)。看了看發現不是，然後就直接

dp

吧。然後發現和

lcs

思考過程一模一樣…

做完之後看了三葉姐的題解，深受啟發。 【宮水三葉の相信科學系列】求「最值問題」隻需要確定「不漏」即可

• 時間複雜度： O ( n m ) O(nm) O(nm)。
• 空間複雜度： O ( n m ) O(nm) O(nm)

代碼：

寫法一：四種情況的分類劃分，狀态之間有重疊，但不影響最值。經典的 LCS 狀态劃分。

圖檔取自 傳送門：【宮水三葉の相信科學系列】求「最值問題」隻需要確定「不漏」即可。 強烈建議看看分析。再去看看 [線性dp] aw897. 最長公共子序列(重要模闆題+最長公共子序列模型)。

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 ++ ) {
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                if (nums1[i - 1] == nums2[j - 1]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
            }

        return f[n][m];
    }
};
           

寫法二：LCS 的優化，僅判斷

a[i]==b[j]

，隻分兩種情況，狀态轉移加

if-else

，代碼結構與樸素版的一樣。更加簡潔。

其實經過仔細比對，會發現，當

a[i]==b[j]

時，狀态一定由

f[i-1][j-1]+1

進行轉移，就不需要通過

f[i][j] = max(f[i - 1][j], f[i][j - 1]);

這個轉移了。但樸素的寫法，會将這個放到前面，使其先判斷不等，再判斷相等。

重點了解：

• 其中，

  a[i]==b[j]

  隻需要

  f[i][j]=f[i-1][j-1]+1

  參與狀态轉移，而不需要其它的來進行大小比較。例如和四種狀态劃分一樣，當

  a[i]==b[j]

  時，

  f[i][j]=max(f[i-1][j],f[i][j-1],f[i-1][j-1]+1)

  這三個值來比大小。以其中一個為例，

  f[i][j-1]

  相較于

  f[i-1][j-1]+1

  是多了一個

  a[i]

  元素的，那麼如果這個

  a[i]

  元素比對了

  b

  串中的某一個，也不過是

  +1

  的貢獻量，頂多與

  f[i-1][j-1]+1

  持平。如果不比對，甚至還不如

  f[i-1][j-1]+1

  ，那麼取

  max

  自然取不到它。 是以直接通過

  f[i][j]=f[i-1][j-1]+1

  進行狀态轉移。
• 是以，在

  a[i]==b[j]

  狀态轉移時進行一個小優化。兩種方法的代碼實作将完全一緻。

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] = f[i - 1][j - 1] + 1;    // 直接轉移
                else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            }

        return f[n][m];
    }
};