本文主要是介绍leetcode 198. House Robber(python3),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目 :House Robber
题目分析:
强盗只能间隔着抢钱,连续抢就会被发现,当输入为【1,2,3,1】输出,1+3=4 ,输入为【2,7,9,3,1】输出为2+9+1=12
输入为【2,1,2,4】输出为2+4=6
编程思路:
1 .题目要求输入为列表,输出为整型
2.实际含义。
f(0) = nums[0] #输入只有一个数时,取第一个
f(1) = max(num[0], num[1]) #输入有2个数时,比较大小,取最大那个
f(2) = man(f(0)+nums[2],f(1)) #输入为3个数时,比较1与3的和与2的大小,取最大
f(k) = max( f(k-2) + nums[k], f(k-1) ) #输入为k个数时,比较f(k-2)与最后一个数的和f(k-1)#的大小,取最大值
程序代码:
class Solution:def rob(self, nums):""":type nums: List[int]:rtype: int"""if not nums: #输入0个数return 0elif len(nums) == 1: #输入1给数时return nums[0]else: #输入2个数以上dp = [0] * len(nums)dp[0] = nums[0]dp[1] = max(nums[0], nums[1])for i in range(2, len(nums)):dp[i] = max(nums[i] + dp[i-2], dp[i-1])return dp[-1] # return the last element #返回最后一个元素
这篇关于leetcode 198. House Robber(python3)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!