Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给定一个数组,不可以取相邻的数,问从中取出一些数,获得的最大和是多少,简单DP,状态转移方程:

dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]) (当前步骤不取,或者取了上上一个数,再取当前数)

 1 #198
 2 #Runtime: 19 ms (Beats 88.86%)
 3 #Memory: 13.5 MB (Beats 43.78%)
 4 
 5 class Solution(object):
 6     def rob(self, nums):
 7         """
 8         :type nums: List[int]
 9         :rtype: int
10         """
11         dp = [0] * (len(nums) + 1)
12         dp[1] = nums[0]
13         for i in range(2, len(nums) + 1):
14             dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1])
15         return max(dp)

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