化簡無所不在 用數列DP來解 給定公差的最長等差數列 Leetcode #1218

Distillery Images on Unsplash

題目敘述 Longest Arithmetic Subsequence of Given Difference

給定一個整數陣列nums，請找出給定公差difference的最長的等差數列的長度是多少?

測試範例

Example 1:

Input: arr = [1,2,3,4], difference = 1
Output: 4
Explanation: The longest arithmetic subsequence is [1,2,3,4].

1->2->3->4 公差為1的最長等差數列長度為4

Example 2:

Input: arr = [1,3,5,7], difference = 1
Output: 1
Explanation: The longest arithmetic subsequence is any single element.

只能各自落單，公差為1的最長等差數列長度為1​

Example 3:

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].

7->5->3->1，公差為1的最長等差數列長度為4

約束條件

Constraints:

• 1 <= arr.length <= 10^5

輸入陣列長度介於1~十萬之間，保證至少有兩項。

• -10^4 <= arr[i], difference <= 10^4

每個陣列元素介於 負一萬~正一萬 之間。

觀察

怎樣叫做等差數列?

其實就是

後項 - 前項 = 定值= 公差 diff

假如我現在擁有的數字是cur

那我們就可以回頭看，看看前面cur-diff這個數字是否存在?

如果cur-diff存在，連到我自己這一項cur，公差為diff的等差數列長度再+1。

想成比較嚴謹的數學型式，就是

DP[ cur ] = DP[ cur - diff ] + 1,

where diff = 題目給定的公差

對應的教學影片

演算法 DP動態規劃

1.定義DP狀態

定義DP[ cur ] 代表以cur作為結尾，伴隨公差為diff的等差數列最大長度。

最後所求就是所有等差數列的最大值

= Max{ 整張DP表格 }

= Max{ DP table }

2.推導DP狀態轉移關係式

假如我現在擁有的數字是cur

那我們就可以回頭看，看看前面cur-diff這個數字是否存在?

如果cur-diff存在，連到我自己這一項cur，公差為diff的等差數列長度再+1。

想成比較嚴謹的數學型式，就是

DP[ cur ] = DP[ cur - diff ] + 1,

where diff = 題目給定的公差

3.釐清DP初始狀態

最小規模的問題是什麼?

當只剩下一個數字的時候，數列長度自然是1

DP[ cur ] = 1

程式碼 DP動態規劃

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:

        ## DP Table
        # key: tail number of subsequence
        # value: length of subsequence
        dp = defaultdict(int)
        
        # Scan each number
        for cur in arr:
            
            # Use current number as tail of subsequence
            # Update length of arithmetic subsequence with given difference

            # ..., (cur - difference), ..., cur, ...
            dp[ cur ] = dp[ cur - difference ] + 1
        
        # Max length of arithmetic subsequence with given difference
        return max( dp.values() )

複雜度分析

時間複雜度:O(n)

線性掃描每個數字，每個數字可以在O(1)計算等差數列延伸後的長度。

空間複雜度: O(n)

DP table 所需空間大小為O(n)，紀錄以每個數字為結尾的等差數列最大長度。

關鍵知識點

使用到數列題實用的"回頭看"的技巧。

在這題，就是回頭看，回頭找前一項去延伸等差數列，並且記錄等差數列的長度。

強烈建議複習

用DP框架來思考 最長的等差數列Longest Arithmetic Subsequence_Leetcode#1027

鞏固知識點，加深印象。

Reference

[1] Longest Arithmetic Subsequence of Given Difference - LeetCode

回到DP特訓班目錄 和 學習路徑