Posted on 2023-08-26 19:46
Uriel 阅读(26)
评论(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)