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

Jonas Jacobsson on Unsplash

題目敘述 Longest Arithmetic Subsequence

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

測試範例

Example 1:

Input: nums = [3,6,9,12]
Output: 4
Explanation:  The whole array is an arithmetic sequence with steps of length = 3.

3, 6, 9, 12
等差數列最大長度為4​

Example 2:

Input: nums = [9,4,7,2,10]
Output: 3
Explanation:  The longest arithmetic subsequence is [4,7,10].

4, 7, 10
等差數列最大長度為3​

Example 3:

Input: nums = [20,1,15,3,10,5,8]
Output: 4
Explanation:  The longest arithmetic subsequence is [20,15,10,5].

20, 15, 10, 5
等差數列最大長度為4

約束條件

Constraints:

• 2 <= nums.length <= 1000

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

• 0 <= nums[i] <= 500

每個陣列元素介於0~500之間。

對應的教學影片

觀察

怎樣叫做等差數列?

其實就是

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

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

那我們就可以回頭看，看看前面index before所對應的數字b對應公差diff的等差數列長度是多少，

連到我自己這一項，長度再+1。

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

DP[ cur ][ diff ] = DP[ before ][ diff ] + 1,
where diff = a - b = nums[cur] - nums[before]

演算法 DP動態規劃

1.定義DP狀態

定義DP[ cur ][ diff ] 代表nums[cur]伴隨公差為diff的等差數列最大長度。

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

= Max{ 整張DP表格 }

= Max{ DP table }

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

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

那我們就可以回頭看，看看前面index before所對應的數字b對應公差diff的等差數列長度是多少，

連到我自己這一項，長度再+1。

想成比較DP的狀態轉移關係式，就是

DP[ cur ][ diff ] = DP[ before ][ diff ] + 1,
where diff = a - b = nums[cur] - nums[before]

3.釐清DP初始狀態

最小規模的問題是什麼?

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

DP[ index ][ diff ] = 1 作為初始值

程式碼 DP動態規劃

class Solution:
    def longestArithSeqLength(self, A: List[int]) -> int:
        
        # Quick response on simple case
        # All values are equal, then A is arithmetic sequence with diff = 0
        if min(A) == max(A):
            return len(A)

        ## DP Table
        # key: (index, sequence difference)
        # value: length of arithmetic sequence, ending at specific index
        dp = defaultdict(lambda :1) 

        for cur, a in enumerate(A):
            for before, b in enumerate(A[:cur]):

                diff = a - b
                
                # extend length from subsequence with same difference
                dp[cur, diff] = dp[(before, diff)] + 1
                
        return max( dp.values() )

複雜度分析

時間複雜度:O(n^2)

雙層迴圈，外層迭代index cur, a，內層迭代index before, b，O(n) * O(n) = O(n^2)

空間複雜度: O(n^2)

DP table 所需空間大小為O(n^2)。

關鍵知識點

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

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

Reference

[1] Longest Arithmetic Subsequence - LeetCode

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