专栏首页Android先生每日算法题——打家劫舍

每日算法题——打家劫舍

继续我们的每日算法题系列,有时候你不知道干嘛的时候来上两道算法题,真香~

话不多说,来看看今天的题目,感觉还是比较有意思的:

题目描述

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

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

示例1:

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

示例1:

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

这道题目是一道很典型的 “动态规划” 类算法题目,LZ我在动态规划这类题目上还是偏薄弱,动态规划的精髓就是状态转移方程,通常你遇到这类题目的时候,基本上都是 “找最优解”,“重叠子问题”,一般来说一个大的问题是可以拆成一个个子问题,下面我们来在线分析一下。

解题思路

首先我们来拆分问题,拆成最简单的来看:

1、当只有1间房的时候,我们没有选择,只能选择抢劫这间房; 2、当有两间房的时候,我们可以比较哪间房里面的钱多,抢劫钱多的房间就好了; 3、当有三间房的时候,有两种方案,抢1,3号房间/抢2号房间的,比较一下哪种方案多; 4、当有四间房的时候,因为我们已经知道了1,2,3间房时能获取到的最大金额,所以我们只需要将抢第四间房的金额数加上抢第二间房能获取到的最大金额数来和第三间房进行比较,取最大值就好了。

相信写到这里大家应该就能看出来状态转移方程是什么了吧,当我们抢劫第 i 间房的时候,我们需要比较一下第 i-2 间房所能获取到的最大金额数加上当前房间的金额数和第 i-1 间房所能获取到的最大金额数哪个大;我们用一个数组来保存抢劫金额的最大数,于是就有了,f[n] = Math.max(f[n-2] + money[n], f[n-1])

题解

public int rob(int[] nums) {
    if (null == nums || nums.length == 0) {
        return 0;
    }
    int len = nums.length;
    if (len == 1) {
        return nums[0];
    }
    if (len == 2) {
        return Math.max(nums[0], nums[1]);
    }
    //上述判断是将最简单的几种情况先计算好,也是为了初始化momey[0] 和 money[1]

    // 定义一个数组,用来保存打劫 0 - (len-1) 家最大能打劫到的金额数
    int[] money = new int[len];
    money[0] = nums[0];
    money[1] = Math.max(nums[0], nums[1]);
    for (int i = 2; i < len; i++) {
        money[i] = Math.max(money[i - 2] + nums[i], money[i - 1]);
    }
    return money[len - 1];
}

本文分享自微信公众号 - IT先森养成记(cyg_24kshign),作者:24K纯帅豆

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

原始发表时间:2020-02-24

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每日算法题——两数之和

    许久不见,终于开始在公司上班了,有一点不好的就是一整天都要戴着口罩,闷得慌,不知道大伙儿有没有这种感觉。

    用户2802329
  • Fragment全解析系列(二):正确的使用姿势

    Fragment是可以让你的app纵享丝滑的设计,如果你的app想在现在基础上性能大幅度提高,并且占用内存降低,同样的界面Activity占用内存比Fragme...

    用户2802329
  • 面试常见算法——连续子序列问题

    新的一周,又到了上班的日子了,由于新型肺炎病毒还在持续,有些人可能收到通知还是在家里远程办公,但是有些人可能公司就要求回去公司上班了,在这里还是要提醒大家,无论...

    用户2802329
  • 【LeetCode】55. 跳跃游戏

    输入: [2,3,1,1,4] 输出: true 解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。...

    韩旭051
  • leetcode-506-Relative Ranks

    chenjx85
  • Leetcode——刷题删除重复出现的元素

    给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

    润森
  • LeetCode 724. 寻找数组的中心索引

    我们是这样定义数组中心索引的:数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。

    Michael阿明
  • 经典故障分析 - ASSM引发的索引争用与 enq HW -contention 等待事件

    作者介绍: 孙加鹏 云和恩墨技术顾问 六年Oracle技术顾问经验,所服务的行业包括电信运营商、金融业、制造业等。 擅长Oracle的故障诊断、高可用架构、升级...

    数据和云
  • 删除排序数组中的重复数字

    一份执着✘
  • 扑克牌中的顺子

    从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的。2~10为数字本身,A为1,J为11,Q为12,K为13,而大、小王为 0 ,可以看成任意数...

    木子星兮

扫码关注云+社区

领取腾讯云代金券