Leetcode Q.1626 [Medium]: Knapsack DP

You are the manager of a basketball team. For the upcoming tournament, you want to choose the team with the highest overall score. The score of the team is the sum of scores of all the players in the team.

However, the basketball team is not allowed to have conflicts. A conflict exists if a younger player has a strictly higher score than an older player. A conflict does not occur between players of the same age.

Given two lists, scores and ages, where each scores[i] and ages[i] represents the score and age of the ith player, respectively, return the highest overall score of all possible basketball teams.

 

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. 
 

 

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        team = list(zip(ages,scores))
        team.sort()
        dp = [pair[1] for pair in team]
        # same as
        # dp = []
        # for i in ans:
        #   dp.append(i[1])

        for i in range(1, len(team)):
            for j in range(i):
                if team[i][1] >= team[j][1]:
                    dp[i] = max(dp[i], dp[j]+team[i][1])

        return max(dp)

 

1. zip()으로 age와 scores를 하나로 묶어준다

2. 이후 sort()로 순서대로 바꿔주어 계산을 편하게 한다

3. dp list를 만든다

   3-1. dp = [pair[1] for pair in team] 은

   3-2. for i in team: dp.append(i[1]) 과 같다

4. 이후 뒤의 값만 비교하기 위해 nested for loop을 사용한다

5. the inner loop compares each player 'i' with every previous player 'j' to check if 'i' can be added to the team

6. the condition checks ensures that adding player 'i' to the tam will not violate the no-conflict condition

7. if player 'i' can be added, then dp[i] is updated to reflect the maximum possible score by either keeping the current score 'dp[i]' or updating it to dp[j] + team[i][1]

8. return the maximum number