博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
lc198. House Robber
阅读量:5823 次
发布时间:2019-06-18

本文共 1464 字,大约阅读时间需要 4 分钟。

  1. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4. Example 2:

Input: [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.

思路:动态规划,参考 字典存1,2,3等各种情况返回的值 注意边界值

f(1) = num[0]f(2) = max(num[0],num[1])f(3) = max(num[0]+num[2],num[1])f(n) = max(num[n-1]+f(n-2),f(n-1))复制代码

代码:python3

class Solution:    def rob(self, nums: List[int]) -> int:        dp={}        if len(nums) == 0:            return 0        if len(nums) == 1:            return nums[0]        if len(nums) == 2:            return max(nums[0],nums[1])        dp[0] = nums[0]            dp[1] = max(nums[0],nums[1])        for i in range(2,len(nums)):            dp[i]=max(dp[i-2]+nums[i],dp[i-1])        return dp[len(nums)-1]复制代码

转载于:https://juejin.im/post/5ce4ea3df265da1bc94ec481

你可能感兴趣的文章
Frank Klemm's Dither and Noise Shaping Page: Dither and Noise Shaping In MPC/MP+
查看>>
网络抓包的部署和工具Wireshark【图书节选】
查看>>
Redis在Windows+linux平台下的安装配置
查看>>
Maven入门实战笔记-11节[6]
查看>>
Local declaration of 'content' hides instance variable
查看>>
ASP.NET中 HTML标签总结及使用
查看>>
Linux下日志系统的设计
查看>>
爬虫IP被禁的简单解决方法——切换UserAgent
查看>>
selenium + python 添加等待时间
查看>>
php生成word,并下载
查看>>
python 函数参数
查看>>
紫书 习题8-11 UVa 1615 (区间选点问题)
查看>>
asp.net mvc学习(Vs技巧与Httpcontext)
查看>>
float数据在内存中是怎么存储的
查看>>
开发经验和习惯
查看>>
dedecms 修改标题长度可以修改数据库
查看>>
Matplotlib学习---用matplotlib画直方图/密度图(histogram, density plot)
查看>>
MySQL案列之主从复制出错问题以及pt-slave-restart工具的使用
查看>>
linux 查看剩余内存数
查看>>
测试人员容易遗漏的隐藏缺陷
查看>>