class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
if n == 0: return 0
dp = [1] * n
ans = 1
for i in range(n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
ans = max(ans, dp[i])
return ans
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
n = len(intervals)
if n == 0: return 0
dp = [1] * n
ans = 1
intervals.sort(key=lambda a: a[0])
for i in range(len(intervals)):
for j in range(i - 1, -1, -1):
if intervals[i][0] >= intervals[j][1]:
dp[i] = max(dp[i], dp[j] + 1)
break # 由于是按照开始时间排序的, 因此可以剪枝
return n - max(dp)
class Solution:
def findLongestChain(self, intervals: List[List[int]]) -> int:
n = len(intervals)
if n == 0: return 0
dp = [1] * n
ans = 1
intervals.sort(key=lambda a: a[0])
for i in range(len(intervals)):
for j in range(i - 1, -1, -1):
if intervals[i][0] > intervals[j][1]:
dp[i] = max(dp[i], dp[j] + 1)
break # 由于是按照开始时间排序的, 因此可以剪枝
return max(dp)
class Solution:
def findMinArrowShots(self, intervals: List[List[int]]) -> int:
n = len(intervals)
if n == 0: return 0
dp = [1] * n
ans = 1
intervals.sort(key=lambda a: a[0])
for i in range(len(intervals)):
for j in range(i - 1, -1, -1):
if intervals[i][0] > intervals[j][1]:
dp[i] = max(dp[i], dp[j] + 1)
break # 由于是按照开始时间排序的, 因此可以剪枝
return max(dp)
复杂度分析
时间复杂度：$O(N ^ 2)$
空间复杂度：$O(N)$
优化
大家想看效率高的，其实也不难。 LIS 也可以用 贪心 + 二分 达到不错的效率。代码如下：
代码文字版如下：
class Solution:
def lengthOfLIS(self, A: List[int]) -> int:
d = []
for a in A:
i = bisect.bisect_left(d, a)
if i < len(d):
d[i] = a
elif not d or d[-1] < a:
d.append(a)
return len(d)
如果求最长不递减子序列呢？
我们只需要将最左插入改为最右插入即可。代码：
class Solution:
def lengthOfLIS(self, A: List[int]) -> int:
d = []
for a in A:
# 这里改为最右
i = bisect.bisect(d, a)
if i < len(d):
d[i] = a
# 这里改为小于等号
elif not d or d[-1] <= a:
d.append(a)
return len(d)
最左插入和最右插入分不清的可以看看我的二分专题。
也可以这么写，更简单一点：
def LIS(A):
d = []
for a in A:
# 如果求要严格递增就改为最左插入 bisect_left 即可
i = bisect.bisect(d, a)
if i == len(d):
d.append(a)
elif d[i] != a:
d[i] = a
return len(d)
class Solution:
def pileBox(self, box: List[List[int]]) -> int:
box = sorted(box, key=sorted)
n = len(box)
dp = [0 if i == 0 else box[i - 1][2] for i in range(n + 1)]
ans = max(dp)
for i in range(1, n + 1):
for j in range(i + 1, n + 1):
if box[j - 1][0] > box[i - 1][0] and box[j - 1][1] > box[i - 1][1] and box[j - 1][2] > box[i - 1][2]:
dp[j] = max(dp[j], dp[i] + box[j - 1][2])
ans = max(ans , dp[j])
return ans
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
if not envelopes: return 0
n = len(envelopes)
dp = [1] * n
envelopes.sort()
for i in range(n):
for j in range(i + 1, n):
if envelopes[i][0] < envelopes[j][0] and envelopes[i][1] < envelopes[j][1]:
dp[j] = max(dp[j], dp[i] + 1)
return max(dp)
class Solution:
def minDeletionSize(self, A):
keep = 1
m, n = len(A), len(A[0])
dp = [1] * n
for j in range(n):
for k in range(j + 1, n):
if all([A[i][k] >= A[i][j] for i in range(m)]):
dp[k] = max(dp[k], dp[j] + 1)
keep = max(keep, dp[k])
return n - keep
class Solution:
def minOperations(self, target: List[int], A: List[int]) -> int:
def LIS(A):
d = []
for a in A:
i = bisect.bisect_left(d, a)
if d and i < len(d):
d[i] = a
else:
d.append(a)
return len(d)
B = []
target = { t:i for i, t in enumerate(target)}
for a in A:
if a in target: B.append(target[a])
return len(target) - LIS(B)
class Solution:
def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
n = len(scores)
persons = list(zip(ages, scores))
persons.sort(key=lambda x : (x[0], x[1]))
dp = [persons[i][1] for i in range(n)]
for i in range(n):
for j in range(i):
if persons[i][1] >= persons[j][1]:
dp[i] = max(dp[i], dp[j]+persons[i][1])
return max(dp)
class Solution:
def solve(self, nums):
n = len(nums)
ans = 1
def LIS(A):
d = []
for a in A:
i = bisect.bisect_left(d,a)
if i == len(d): d.append(a)
else: d[i] = a
return len(d)
nums += nums
for i in range(n):
ans = max(ans , LIS(nums[i:i+n]))
return ans
