646. 最長數對鏈 : 常規貪心 DP 運用題

語言: CN / TW / HK

時間 2022-09-03 13:48:58 SegmentFault部落格

主題: 技術

題目描述

這是 LeetCode 上的 646. 最長數對鏈 ，難度為中等。

Tag : 「貪心」、「排序」、「二分」、「序列 DP」、「LIS」

給出 n 個數對。在每一個數對中，第一個數字總是比第二個數字小。

現在，我們定義一種跟隨關係，當且僅當 b < c 時，數對 $(c, d)$ 才可以跟在 $(a, b)$ 後面。我們用這種形式來構造一個數對鏈。

給定一個數對集合，找出能夠形成的最長數對鏈的長度。你不需要用到所有的數對，你可以以任何順序選擇其中的一些數對來構造。

示例：

輸入：[[1,2], [2,3], [3,4]]

輸出：2

解釋：最長的數對鏈是 [1,2] -> [3,4]

提示：

給出數對的個數在 $[1, 1000]$ 範圍內。

排序 + 貪心 DP（轉移剪枝）

起始先將 pairs 根據第一維排升序（或直接雙關鍵字排升序）。

考慮定義 $f[i]$ 為以 $pairs[i]$ 為結尾的最長數對鏈長度，所有 $f[i]$ 中的最大值為答案。

不失一般性考慮 $f[i]$ 該如何轉移：不難發現 $f[i]$ 為所有滿足「下標範圍在 $[0, i - 1]$，且 $pairs[j][1] < pairs[i][0]$」條件的 $f[j] + 1$ 的最大值。

但實際上，我們只需要從 $j = i - 1$ 開始往回找，找到第一個滿足 $pairs[j][1] < pairs[i][0]$ 的位置 $j$ 即可。

容易證明該做法的正確性：假設貪心解（該做法）找到的位置 $j$ 不是最優位置，即存在比 $j$ 更小的合法下標 $j'$ 滿足 $f[j'] > f[j]$。根據我們的排序規則必然有 $pairs[j'][0] <= pairs[j][0]$ 的性質，則可知 $pairs[j]$ 必然可以代替 $pairs[j']$ 接在原本以 $pairs[j']$ 為結尾的最優數鏈上（最優數鏈長度不變，結果不會變差），則至少有 $f[j'] = f[j]$。

程式碼：

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a,b)->a[0]-b[0]);
        int n = pairs.length, ans = 1;
        int[] f = new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = i - 1; j >= 0 && f[i] == 1; j--) {
                if (pairs[j][1] < pairs[i][0]) f[i] = f[j] + 1;
            }
            ans = Math.max(ans, f[i]);
        }
        return ans;
    }
}

DP

排序 + 貪心 DP（優化轉移）

根據上述分析，我們知道對於一個特定的 $pairs[i]$ 而言，其所有合法（滿足條件 $pairs[j][1] < pairs[i][0]$）的前驅狀態 $f[j]$ 必然是非單調遞增的。

根據 LIS 問題的貪心解的思路，我們可以額外使用一個數組記錄下特定長度數鏈的最小結尾值，從而實現二分找前驅狀態。

具體的，建立 $g$ 陣列，其中 $g[len] = x$ 代表數鏈長度為 $len$ 時結尾元素的第二維最小值為 $x$。

如此一來，當我們要找 $f[i]$ 的前驅狀態時，等價於在 $g$ 陣列中找滿足「小於 $pairs[i][0]$」的最大下標。同時，我們不再需要顯式維護 $f$ 陣列，只需要邊轉移變更新答案即可。

不瞭解 LIS 問題的同學可以看前置 : LCS 問題與 LIS 問題的相互關係，以及 LIS 問題的最優解證明 :tada::tada::tada:

程式碼：

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a,b)->a[0]-b[0]);
        int n = pairs.length, ans = 1;
        int[] g = new int[n + 10];
        Arrays.fill(g, 0x3f3f3f3f);
        for (int i = 0; i < n; i++) {
            int l = 1, r = i + 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (g[mid] >= pairs[i][0]) r = mid;
                else l = mid + 1;
            }
            g[r] = Math.min(g[r], pairs[i][1]);
            ans = Math.max(ans, r);
        }
        return ans;
    }
}

DP

最後

這是我們「刷穿 LeetCode」系列文章的第 No.646 篇，系列開始於 2021/01/01，截止於起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們將先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的程式碼。如果涉及通解還會相應的程式碼模板。

為了方便各位同學能夠電腦上進行除錯和提交程式碼，我建立了相關的倉庫： https://github.com/SharingSou... 。

在倉庫地址裡，你可以看到系列文章的題解連結、系列文章的相應程式碼、LeetCode 原題連結和其他優選題解。

更多更全更熱門的「筆試/面試」相關資料可訪問排版精美的合集新基地 :tada::tada:

本文由mdnice多平臺釋出

「其他文章」