专栏首页木又AI帮【leetcode刷题】T161-打家劫舍

【leetcode刷题】T161-打家劫舍

https://leetcode-cn.com/problems/house-robber/

【题目】

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

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

示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

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

【思路】

动态规划递推公式为:dp[i] = max(dp[i-1], dp[i-2] + nums[i])

dp[i]表示从0->i能偷窃到的最高金额,那么值只有两个来源,偷窃第i家,值为dp[i-2] + nums[i];不偷窃第i家,值为dp[i-1]。

我们可以看到,循环从头至尾,只涉及前两个值,因此可以不用数组, 只使用两个变量。

(python使用数组,c++使用变量)

【代码】

python版本

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        if len(nums) == 0:
            return 0
        if len(nums) < 2:
            return max(nums)
        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(dp[i-1], dp[i-2] + nums[i])
        return dp[-1]

C++版本

class Solution {
public:
    int rob(vector<int>& nums) {
        // dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        if(nums.size() == 0)
            return 0;
        if(nums.size() < 2)
            return max(nums.front(), nums.back());
        int a = nums[0];
        int b = max(nums[0], nums[1]);
        int tmp;
        for(int i=2; i < nums.size(); i++){
            tmp = b;
            b = max(b, a + nums[i]);
            a = tmp;
        }
        return b;
    }
};

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java的this和重载

    2、表示用类的成员变量,而非函数参数,注意在函数参数和成员变量同名是进行区分!其实这是第一种用法的特例,比较常用,所以那出来强调一下。

    用户5224393
  • Java数组

    数组对于每一门编程语言来说都是重要的数据结构之一,当然不同语言对数组的实现及处理也不尽相同。

    用户5224393
  • 【深度知识】Rust语言入门、关键技术与实战经验

    编者按:高可用架构分享及传播在架构领域具有典型意义的文章,本文由唐刘在高可用架构群分享。转载请注明来自高可用架构公众号「 ArchNotes 」。

    辉哥
  • Java之非访问修饰符

    final 修饰符,用来修饰类、方法和变量,final 修饰的类不能够被继承,修饰的方法不能被继承类重新定义,修饰的变量为常量,是不可修改的。

    用户5224393
  • Java之接口详解

    接口(英文:Interface),就是比“抽象类”还“抽象”的“抽象类”,可以更加规范的对子类进行约束。全面地专业地实现了,规范和具体实现的分离。

    用户5224393
  • Java之抽象

    在面向对象的概念中,所有的对象都是通过类来描绘的,但是反过来,并不是所有的类都是用来描绘对象的,如果一个类中没有包含足够的信息来描绘一个具体的对象,这样的类就是...

    用户5224393
  • Java基本数据类型的包装类

    Java语言是一个面向对象的语言,但是Java中的基本数据类型却是不面向对象的,这在实际使用时存在很多的不便,为了解决这个不足,在设计类时为每个基本数据类型设计...

    用户5224393
  • 初学者第67节多线程之单例模式(十)

    java中单例模式是一种常见的设计模式,单例模式的写法有好几种,这里主要介绍三种:懒汉式单例、饿汉式单例、登记式单例。   单例模式有以下特点:   1、单例类...

    用户5224393
  • Java内部类详解

    内部类(nested classes),面向对象程序设计中,可以在一个类的内部定义另一个类。嵌套类分为两种,即静态嵌套类和非静态嵌套类。

    用户5224393
  • Java面试题-基础篇二

    不可以。因为非static方法是要与对象关联在一起的,必须创建一个对象后,才可以在该对象上进行方法调用,而static方法调用时不需要创建对象,可以直接调用。

    用户5224393

扫码关注云+社区

领取腾讯云代金券