题解 | #打家劫舍(一)#

题目链接

题目描述

描述

你是一个经验丰富的小偷，准备偷沿街的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家；如果偷了第二家，那么就不能偷第一家和第三家。给定一个整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。

alt

示例1

输入：

[1,2,3,4]

返回值：

说明：

最优方案是偷第 2，4 个房间

示例2

输入：

[1,3,6]

返回值：

说明：

最优方案是偷第 1，3个房间

示例3

输入：

[2,10,5]

返回值：

说明：

最优方案是偷第 2 个房间

解题思路

简单dp，对于每个房间只有偷不偷两种，你是一个小偷，你也不知道后面有多少。

当我们访问房间i时，我们只有两种选择：偷i，并且拿起i-2及以前所有的财富；不偷i，拿起i-1及以前所有的财富。我们可以保证我们访问第i间房间时，拿到的钱是最多的。

这就很好解决了，用一个数组存储累加的数就好，最后最多的财富值就是数组最后一项的值。

题解

//打家劫舍（一）
function rob(nums) {
    // write code here
    let stealList = [];
    let max = 0;
    stealList[0] = nums[0];
    stealList[1] = nums[0] > nums[1] ? nums[0] : nums[1];
    for (let i = 2; i < nums.length; i++) {
        let s = stealList[i - 2] + nums[i];
        if (stealList[i - 1] > s)
            s = stealList[i - 1];
        stealList[i] = s;
    }
    return stealList[nums.length - 1];
}
console.log(rob([1, 2, 3, 4]));
module.exports = {
    rob: rob
};