Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
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)

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理