Given the age and score of each players. Selected some of them to obtain the maximum total score and make sure that all the selected players with a younger age do not have a higher score than older ones (could be the same score).
Two ways to do DP
Approach 1: zip the age and score of each player, sort by score, then go through all the players' age and sco, update dp matrix as:
dp[age] = max(dp[:age+1]) + sco
return max(dp)
Approach 2: zip the age and score of each player, sort by age, then go through all the players i, update dp matrix as:
dp[i] = max(dp[i], dp[j] + scores_sorted_by_age[i][1]), while j < i and scores_sorted_by_age[j][1] <= scores_sorted_by_age[i][1]:
return max(dp)
- Time complexity:
Both methods are O(n^2)
- Space complexity:
Both methods are O(n)
Approach 1:
1 #1626
2 #Runtime: 285 ms (Beats 100%)
3 #Memory 13.8 MB (Beats 80%)
4
5 class Solution(object):
6 def bestTeamScore(self, scores, ages):
7 """
8 :type scores: List[int]
9 :type ages: List[int]
10 :rtype: int
11 """
12 dp = [0] * (max(ages) + 1)
13 scores_sorted_by_scores = sorted(zip(scores, ages))
14 for sco, age in scores_sorted_by_scores:
15 dp[age] = max(dp[:age+1]) + sco
16 return max(dp)
Approach 2:
1 #1626
2 #Runtime: 1532 ms (Beats 55%)
3 #Memory: 13.9 MB (Beats 65%)
4
5 class Solution(object):
6 def bestTeamScore(self, scores, ages):
7 """
8 :type scores: List[int]
9 :type ages: List[int]
10 :rtype: int
11 """
12 dp = [0] * len(ages)
13 scores_sorted_by_age = sorted(zip(ages, scores))
14 for i in range(len(ages)):
15 dp[i] = scores_sorted_by_age[i][1]
16 for j in range(i):
17 if scores_sorted_by_age[j][1] <= scores_sorted_by_age[i][1]:
18 dp[i] = max(dp[i], dp[j] + scores_sorted_by_age[i][1])
19 return max(dp)