文档章节

leetcode 198 打家劫舍 Python 动态规划

o
 osc_gu9d45li
发布于 2019/04/20 20:40
字数 432
阅读 12
收藏 0

精选30+云产品,助力企业轻松上云!>>>

打家劫舍

 

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
    偷窃到的最高金额 = 1 + 3 = 4 。
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
    偷窃到的最高金额 = 2 + 9 + 1 = 12 。




动态规划1:(我的混乱的思绪 唉~~~ 既然不允许偷两个连续的房间 那么记录 当前-2 和当前-3 这两个
class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]
        if len(nums) == 2:
            return max(nums[0],nums[1])
        df = [0 for x in range(len(nums))]
        df[0] = nums[0]
        df[1] = max(nums[0],nums[1])
        df[2] = max(nums[0] + nums[2], nums[1])
        max_ = df[2]
    
for i in range(3,len(nums)): df[i] = max(df[i-2],df[i-3]) + nums[i] if df[i] > max_: max_ = df[i] return max_

动态规划另一个清晰实现:

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:return 0
        dp = [0 for i in range(len(nums)+1)]
        for i in range(1,len(nums)+1):
            if i==1:
                dp[1] = nums[0]
            else:
                dp[i] = max(dp[i-1],dp[i-2]+nums[i-1])
        return dp[-1]

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
(leetcode:选择不相邻元素,求和最大问题):打家劫舍(DP:198/213/337)

题型:从数组中选择不相邻元素,求和最大 (1)对于数组中的每个元素,都存在两种可能性:(1)选择(2)不选择,所以对于这类问题,暴力方法(递归思路)的时间复杂度为:O(2^n); (2)递归...

osc_y7ckpzr9
2019/04/27
2
0
[LeetCode] 213. House Robber II 打家劫舍 II

Note: This is an extension of House Robber. After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much ......

osc_flp5mhtj
2018/03/26
12
0
[LeetCode] 198. 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......

osc_flp5mhtj
2018/03/26
4
0
[LeetCode] 337. House Robber III 打家劫舍 III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one par......

osc_flp5mhtj
2018/03/26
11
0
LeetCode 思路及解答

终于作为转专业小白的我也开始刷题啦!希望能通过记录分享的形式加深解题思路的理解和记忆。也希望大神们能够指点一二。 列表中的题目名称都是链接,难度和标签也都是也都是链接,方便归类搜...

osc_cyiu3qx7
2018/06/29
2
0

没有更多内容

加载失败,请刷新页面

加载更多

linux下java环境搭建

1、jdk下载: 官方地址:https://www.oracle.com/java/technologies/javase/javase-jdk8-downloads.html 如下图所示,我这边选择的是红框中的版本 2、压缩包上传至服务器 将下载的压缩包上传...

wc_飞豆
56分钟前
17
0
面试题:Java对象不再使用时,为什么要赋值为null?

前言 许多Java开发者都曾听说过“不使用的对象应手动赋值为null“这句话,而且好多开发者一直信奉着这句话;问其原因,大都是回答“有利于GC更早回收内存,减少内存占用”,但再往深入问就回...

码农突围
58分钟前
22
0
设计模式(5) 原型模式

原型模式 原型模式的适用场景 浅拷贝 深拷贝 用Initialize方法修改初始化状态 原型模式与之前学习的各种工厂方法、单例模式、建造者模式最大、最直观的区别在于,它是从一个既有的对象“克隆...

zhixin9001
58分钟前
7
0
获取免费的pycharm激活码网站

http://www.lookdiv.com/

云烟成雨forever
58分钟前
27
0
用Helm部署Kubernetes应用,支持多环境部署与版本回滚

1 前言 Helm是优秀的基于Kubernetes的包管理器。利用Helm,可以快速安装常用的Kubernetes应用,可以针对同一个应用快速部署多套环境,还可以实现运维人员与开发人员的职责分离。现在让我们安...

南瓜慢说
59分钟前
25
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部