跳转至

LeetCode: 198.打家劫舍

1、题目描述

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

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

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

2、解题思路

​ 例如:

​ 1,4,3,5,7

​ 我们直接可以看出来,答案应该是11,1+3+7

​ 首先我们要判断当前的值是不是应该添加进去,如何判断呢

​ 假设我们已经计算出了,在这个位置上,前一个值被加上去了,那么当前值不应被加上,

​ 那么我们保存前一次的值,还有更前一次的值,更前一次的值就可以加上当前的值,如果加上以后,结果变大,更新一下,将这个值加上去

​ 前一次和前两次的值都更新

假设prev表示前两次的值,cur表示前一次的值

1,4,3,5,7

一开始,prev=0,cur=0

prev cur nums[i]
0 1 1
1 4 4
4 4 3
4 9 5
9 11 7

实际上,cur表示在前一个位置上能够取到的最大的值

​ prev表示在更前一个位置上能够取到的最大的值

例如(prev = 0)(cur=0)1,2,3,4,5

一开始,我先想要判断1这个位置能够取到的最大的值,就用当前位置的值,加上prev,然后与cur进行比较,取更大的那个

​ 然后prev与cur向右移动

​ 不断的移动,最终,我们得到了当前位置能够取到的最大的值

(prev=0)(cur=0)9,1,1,9

​ 一开始,9+0 > , cur 变成了9, prev还是0

​ 然后,判断1,1+0 <9 , cur 不变,还是9,prev向前移动,变成了9

​ 然后,判断1,1+9 > 9, cur更新成了 10,prev还是9

​ 最后,判断9,9+9>10,cur变成了18,prev变成10

实际上,prev和cur能够延伸当前位置的感知,最多向前感知3个元素,因此覆盖了所有情况

int rob(int* nums, int numsSize) {
    int prev = 0;
    int cur = 0;
    int temp;
    for (int i = 0; i < numsSize; i++) {
        temp = cur;
        cur = prev + nums[i] > cur ? prev + nums[i] : cur;
        prev = temp;

    }

    return cur;
}