LeetCode 精选 TOP 面试题（Java 实现）—— 打家劫舍

一、题目描述

1.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 。

1.2 知识点

• 动态规划

1.3 题目链接

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

二、解题思路

2.1 自研思路

  动态规划标准题型，对于每家只有两种选择，即偷和不偷，如果偷的话则当前的金额最大值应当为到前前家为止能偷的金额最大值加上当前家的金额，如果不偷的话则一定选择偷前一家才能拿到最大值金额，此时的最大金额就等于到前一家为止能偷的最大金额，最后取这两个值中的最大值即可。

三、实现代码

3.1 自研实现

class Solution {
    public int rob(int[] nums) {
    	// cur 为到前一家为止的金额最大值
    	// pre 为到前前一家为止的金额最大值
        int cur = 0, pre = 0;
        for(int num : nums){
            int temp = cur;
            cur = Math.max(pre + num, cur);
            pre = temp;
        }
        return cur;
    }
}