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

語言: CN / TW / HK

題目描述

這是 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多平台發佈