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 0
        dp = [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]*n
        
        for i in range(n):
            score_i = pairs[i][1]
            dp[i] = score_i
            for 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)