LC 1626. 无矛盾的最佳球队

https://leetcode-cn.com/problems/best-team-with-no-conflicts/

回溯肯定是不行的，之后就想到了动态规划。动态规划主要关注状态，基于当前状态如何扩展/更新其他状态。这侧面说明动态规划从在某种计算顺序性，我们大家经常说有子问题最优解结构。这题的一个启示就是，如果题目中含有某种顺序性，就可以尝试动态规划。

这个问题有个隐式顺序性就是年龄和能力的关系，一旦选择了某个年龄下的能力X，那么之后的能力决不能低于X（同年龄除外）。或者换个角度考虑，一旦选择了某个能力下的年龄Y，那么之后的年龄决不能低于Y（同能力的除外）

如果按照第一种思路，得到的解法就是

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        n = len(scores)
        xs = list(zip(ages, scores))
        xs.append((0, 0))
        xs.sort()

        dp = [0] * (n + 1)
        dp[0] = 0
        for i in range(n + 1):
            for j in range(i + 1, n + 1):
                if xs[j][0] == xs[i][0] or xs[j][1] >= xs[i][1]:
                    dp[j] = max(dp[j], dp[i] + xs[j][1])
        ans = max(dp)
        return ans

如果按照第二种思路，得到的解法就是

class Solution2:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        n = len(scores)
        xs = list(zip(scores, ages))
        xs.append((0, 0))
        xs.sort()

        dp = [0] * (n + 1)
        dp[0] = 0
        for i in range(n + 1):
            for j in range(i + 1, n + 1):
                if xs[j][0] == xs[i][0] or xs[j][1] >= xs[i][1]:
                    dp[j] = max(dp[j], dp[i] + xs[j][0])
        ans = max(dp)
        return ans