算法-打家劫舍

1. 最高金额问题

给定一个代表每个房屋存放金额的非负整数数组，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。基于此计算不触动警报装置的情况下 ，小偷一夜之内能够偷窃到的最高金额。LeetCode 原题

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

2. 解法

采用动态规划来解决，需要经过以下步骤：

1. 确定 dp 数组下标含义
   dp[i]：表示下标 i 以内的房屋最多可以偷窃的金额

2. 确定递推关系
   dp[i] 由第 i 个房间偷还是不偷来决定。

   1. 如果偷第 i 房间，那么 dp[i] = dp[i - 2] + nums[i] 。因为第 i-1 房会触发报警，不考虑，此时需取下标 i-2 以内的房屋最多可以偷窃的金额 dp[i-2] 加上第 i 房间能偷到的钱
   2. 如果不偷第 i 房间，那么此时最高金额由第 i-1 房最高金额决定， dp[i] = dp[i - 1]

   因为 dp[i] 需取最大值，即确定递推关系式为 dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])

3. dp数组初始化
   从递推公式 dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]) 可看出递推的基础就是dp[0] 和 dp[1]。此时从 dp[i] 的定义来看，dp[0] 一定是 nums[0]，dp[1] 则是 nums[0] 和 nums[1] 的最大值

    public int rob(int[] nums) {
        if (0 == nums.length) {
            return 0;
        }

        if (1 == nums.length) {
            return nums[0];
        }

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(dp[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[nums.length - 1];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17