化簡無所不在 用數列DP來解 給定公差的最長等差數列 Leetcode #1218
題目敘述 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特訓班目錄 和 學習路徑
你可能也想看
