1.题目描述

198. 打家劫舍

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

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

示例 1:

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

示例 2:

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

2.代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Solution {
    /**
     * leetcode p198 打家劫舍
     * @param num
     * @return
     */
    public static int rob(int[] num) {
        //获取数组的长度
        int length = num.length;

        //移除特殊情况
        if (length == 0){
            return 0;
        }

        //当前位置可盗窃的最大值
        int[] dp = new int[length+1];

        //一些初始值的优化
        dp[0] = 0;
        dp[1] = num[0];

        //枚举每一种情况
        for (int i = 2; i <= length; i++) {
            //注意 i 不是索引 是序号
            //dp[i-2]+num[i-1]
            //dp[i-1]
            dp[i] = Math.max(dp[i-2]+num[i-1],dp[i-1]);
        }

        return dp[length];
    }

    /**
     * 测试程序
     * @param args
     */
    public static void main(String[] args) {
        int[] nums = new int[]{2,7,9,3,1};

        System.out.println(rob(nums));
    }
}

思路描述：

  • 动态规划方程：dp[n] = MAX( dp[n-1], dp[n-2] + num )

  • 由于不可以在相邻的房屋闯入，所以在当前位置 n 房屋可盗窃的最大值，要么就是 n-1 房屋可盗窃的最大值，要么就是 - n-2 房屋可盗窃的最大值加上当前房屋的值，二者之间取最大值

  • 举例来说：1 号房间可盗窃最大值为 33 即为 dp[1]=3，2 号房间可盗窃最大值为 44 即为 dp[2]=4，3 号房间自身的值为 22 即为 num=2，那么 dp[3] = MAX( dp[2], dp[1] + num ) = MAX(4, 3+2) = 5，3 号房间可盗窃最大值为 55