1626. Best Team With No Conflicts
給你很多球員的分數和年齡，要你組建一支總和分數最高的隊伍
隊伍中球員的分數不能超過任何一個年齡比他大的球員的分數
舉例來說，38歲老漢必須是隊伍中分數最高的，因為他年紀最大
Example 1:
Input: scores = [1,3,5,10,15], ages = [1,2,3,4,5]
Output: 34
Explanation: You can choose all the players.
Example 2:
Input: scores = [4,5,6,5], ages = [2,1,2,1]
Output: 16
Explanation: It is best to choose the last 3 players. Notice that you are
allowed to choose multiple people of the same age.
Example 3:
Input: scores = [1,2,3,5], ages = [8,9,10,1]
Output: 6
Explanation: It is best to choose the first 3 players.
思路:
1.題目的意思其實就是如果選進的球員照年齡排序的話，他們的分數必須呈非嚴格遞增
也就是對年齡排序之後找一個總和最大的非嚴格遞增的 subsequence
2.找這種 subsequence 相關的就可以用 dp
dp[i] 代表以 score[i] 為結尾的 subsequence 中最大的總和
那對 j > i 如果 score[i] <= score[j] 就代表說以 score[i] 為結尾的 subsequence
在加進 score[j] 後仍會是非嚴格遞增
也就是說就能用 dp[i] 的結果去更新 dp[j]
可以寫成 dp[j] = max(dp[j], dp[i] + score[j])
最後就看 dp 中哪個值最大就好 因為最大值不一定會發生在 dp[-1]
Python code:
class Solution:
def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
players = list(zip(ages, scores))
players.sort()
n = len(players)
dp = [p[1] for p in players]
res = 0
for i in range(n):
for j in range(i+1, n):
if players[i][1] <= players[j][1]:
dp[j] = max(dp[j], dp[i] + players[j][1])
res = max(res, dp[i])
return res