Leetcode 1626. Best Team With No Conflicts (python)

题目

解析：

对于这种由多个维度的题目，应该基本都是先对一个维度进行一些处理，比如排序，然后再看一个维度固定的情况下，另一个维度上看问题简化成了什么。或者说这个问题是由什么问题包装而来的
这道题目将age进行排序之后，会发现问题简化成了求max sum of non-decreasing sub-sequence。与Leetcode 300. Longest Increasing Subsequence几乎是一样的。这边贴一下lc 300的解法：

class Solution:def lengthOfLIS(self, nums: List[int]) -> int:if not nums:return 0dp = [1]*len(nums)for i in range(len(nums)):for j in range(i):if nums[i]>nums[j]:dp[i] = max(dp[i],dp[j]+1)return max(dp)

转换到这边其实是一样的，只不过那边是累加长度，这边累加sum罢了

class Solution:def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:n = len(scores)pairs = []for i in range(n):pairs.append((ages[i],scores[i]))pairs.sort(key=lambda x:(x[0],x[1]))#print(pairs)dp = [0]*nfor i in range(n):score_i = pairs[i][1]dp[i] = score_ifor j in range(i):score_j = pairs[j][1]if score_j<=score_i:dp[i] = max(dp[i],dp[j]+score_i)return max(dp)