Posted on 2023-08-26 19:46
Uriel 閱讀(37)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
閑來無事重切Leet Code
給出一堆數字pair，pairs[i] = [left
i, right
i] and left
i < right
i，找出最長的一列pair，使得每一個pair的right小于下一個pair的left（pair的順序可以打亂），DP
先將所有pair按right從小到大排序，然后O(n^2)的DP
1 #646
2 #Runtime: 1406 ms (Beats 41.4%)
3 #Memory: 13.8 MB (Beats 67.91%)
4
5 class Solution(object):
6 def findLongestChain(self, pairs):
7 """
8 :type pairs: List[List[int]]
9 :rtype: int
10 """
11 pairs.sort(key=lambda x: x[1])
12 dp = [1] * len(pairs)
13 for i in range(1, len(pairs)):
14 for j in range(i):
15 if pairs[i][0] > pairs[j][1]:
16 dp[i] = max(dp[i], dp[j] + 1)
17 return max(dp)