专栏首页脑洞前端198. 打家劫舍

198. 打家劫舍

题目描述

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

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

示例 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 。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/house-robber 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

这是一道非常典型且简单的动态规划问题,但是在这里我希望通过这个例子, 让大家对动态规划问题有一点认识。

为什么别人的动态规划可以那么写,为什么没有用 dp 数组就搞定了。比如别人的爬楼梯问题怎么就用 fibnacci 搞定了?为什么?在这里我们就来看下。

思路还是和其他简单的动态规划问题一样,我们本质上在解决 对于第[i]个房子,我们抢还是不抢。的问题。

判断的标准就是总价值哪个更大, 那么对于抢的话 就是当前的房子可以抢的价值+dp[i-2]

i - 1 不能抢,否则会触发警铃

如果不抢的话,就是 dp[i-1].

这里的 dp 其实就是 子问题.

状态转移方程也不难写 dp[i]=Math.max(dp[i-2]+nums[i-2],dp[i-1]);.

上述过程用图来表示的话,是这样的:

我们仔细观察的话,其实我们只需要保证前一个 dp[i - 1] 和 dp[i - 2] 两个变量就好了, 比如我们计算到 i = 6 的时候,即需要计算 dp[6]的时候, 我们需要 dp[5], dp[4],但是我们 不需要 dp[3], dp[2] ...

因此代码可以简化为:

let a = 0;
let b = 0;

for (let i = 0; i < nums.length; i++) {
  const temp = b;
  b = Math.max(a + nums[i], b);
  a = temp;
}

return b;

如上的代码,我们可以将复杂度进行优化,从 O(n)降低到 O(1), 类似的优化在 DP 问题中不在少数。

动态规划问题是递归问题查表,避免重复计算,从而节省时间。如果我们对问题加以分析和抽象,有可能对空间上进一步优化

关键点解析

代码

/*
 * @lc app=leetcode id=198 lang=javascript
 *
 * [198] House Robber
 *
 * https://leetcode.com/problems/house-robber/description/
 *
 * algorithms
 * Easy (40.80%)
 * Total Accepted:    312.1K
 * Total Submissions: 762.4K
 * Testcase Example:  '[1,2,3,1]'
 *
 * 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.
 *
 *
 */
/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
  // Tag: DP
  const dp = [];
  dp[0] = 0;
  dp[1] = 0;

  for (let i = 2; i < nums.length + 2; i++) {
    dp[i] = Math.max(dp[i - 2] + nums[i - 2], dp[i - 1]);
  }

  return dp[nums.length + 1];
};

本文分享自微信公众号 - 脑洞前端(fe_lucifer),作者:脑洞很大的程序员

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

原始发表时间:2019-08-15

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 穿上衣服我就不认识你了?来聊聊最长上升子序列

    最长上升子序列是一个很经典的算法题。有的会直接让你求最长上升子序列,有的则会换个说法,但最终考察的还是最长上升子序列。那么问题来了,它穿上衣服你还看得出来是么?

    lucifer210
  • 对《丢鸡蛋问题》的一点补充

    去年的一年时间,我在群里每天都会出题给大家做。但是就在 2020-03 开始,力扣也开展了每日一题活动。我突然觉得这个每日一题的必要性变得小了很多,并且逐渐减少...

    lucifer210
  • 62. 不同路径

    一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

    lucifer210
  • 你的背包,被我找到了(0-1背包问题)

    给你一个可装载重量为W的背包和N个物品,每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i],价值为val[i],现在让你用这个背包装物品,最多能装的...

    五分钟学算法
  • LeetCode 70. Climbing Stairs

    ShenduCC
  • 动态规划此一篇就够了 万字总结

    动态规划,一直以来听着就是一种很高深莫测的算法思想。尤其是上学时候算法的第一堂课,老师巴拉巴拉列了一大堆的算法核心思想,贪心、回溯、动态规划... ...,开始...

    Johngo
  • 告别动态规划,连刷40道动规算法题,我总结了动规的套路

    动态规划难吗?说实话,我觉得很难,特别是对于初学者来说,我当时入门动态规划的时候,是看 0-1 背包问题,当时真的是一脸懵逼。后来,我遇到动态规划的题,看的懂答...

    帅地
  • 画解算法:279. 完全平方数

    https://leetcode-cn.com/problems/perfect-squares/

    灵魂画师牧码
  • 打卡群刷题总结0801——解码方法

    PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

    木又AI帮
  • 巧解动态规划问题

    前言:最近在力扣刷题,但是之前从没有接触过算法题,有的看答案都看不懂,后来做的题做多了发现有好多类似的题目,所以我打算总结一下规律。

    wsuo

扫码关注云+社区

领取腾讯云代金券