【DP】线性排列情况｜Java 刷题打卡

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

一、题目概述

LeetCode 198. 打家劫舍

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

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

示例 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 。
 
复制代码

提示：

0 <= nums.length <= 100
0 <= nums[i] <= 400

题干分析

动态规划标准套路：

1. 第一步要明确：状态 和 选择
2. 第二步要明确：dp 数组的定义
3. 第三步：根据 “选择”，思考状态转移的逻辑

二、思路实现

方案一：

1. 第一步要明确：状态 和 选择

1. 状态：房子的索引
2. 选择：“取钱” 或者 “不取钱”

2. 第二步要明确：dp 数组的定义

1. dp定义：dp(nums, start) = x 表示，从 nums[start] 开始做选择，可以获得的最多的金额为 X。

2. 最终答案：dp(nums, 0)

3. base case：当走过了最后一间房子，就没办法做选择了，能获得的现金数目显然是 0。

3. 第三步：根据 “选择”，思考状态转移的逻辑

1. 如果你取出这间房子的钱，那么对于相邻的下一间房子，肯定不能再取钱了，只能从下下间房子开始做选择。

2. 如果你不取出这间房子的前，那么可以走到下一间房子前，继续做选择。

如图：

在两个选择中，每次都选更大的结果，最后得到的就是最多能取到的钱。

    // 超出时间
    public int rob0(int[] nums) {

        return dp(nums, 0);
    }

    // 返回 nums[start..] 能获得的最大值
    private int dp(int[] nums, int start) {

        if (start >= nums.length) {
            return 0;
        }

        return Math.max(
                // 不取钱，去下间房
                dp(nums, start + 1),
                // 取钱，去下下间房
                nums[start] + dp(nums, start + 2)
        );
    }
复制代码

方案二：在方案一上进行优化

明确了状态转移之后，就可以发现对于同一 start 位置，是存在重叠子问题的，比如下图：

有多种选择可以走到这个位置，而从房间 nums[5..] 中取出的最多值数为一个定值，如果每次执行 dp(nums, 0) 进入递归，岂不是浪费时间？

说明存在重叠子问题，可以用备忘录（数组）进行优化。

1. 第一步要明确：状态 和 选择

1. 状态：房子的索引
2. 选择：“取钱” 或者 “不取钱”

2. 第二步要明确：dp 数组的定义

1. dp[i]定义：dp[i] = x 表示到当前这个房子为止能获取的最大金额为 x

2. 最终答案：dp[nums.length - 1]

3. **base case：dp[0] = nums[0]

3. 第三步：根据 “选择”，思考状态转移的逻辑

1. 如果你取出这间房子的钱，那么对于相邻的下一间房子，肯定不能再取钱了，只能从下下间房子开始做选择。

2. 如果你不取出这间房子的前，那么可以走到下一间房子前，继续做选择。

    public int rob(int[] nums) {

        if (nums == null || nums.length == 0) return 0;

        int [] dp = new int[nums.length];
        // base case 
        dp[0] = nums[0];

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

        d[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; ++i) {

            d[i] = Math.max(d[i - 2] + nums[i], d[i - 1]);
        }

        return d[nums.length - 1];
    }
复制代码

方案三：在方案二上优化

发现状态转移只与 dp[i] 最近的两个状态 dp[i - 2] 和 dp[i - 1] 有关，所以可以进一步优化，将空间复杂度降低到 O(1)

    // Time: o(n), Space: o(1), Faster: 100.00%
    public int rob2(int[] nums) {

        if (nums == null || nums.length == 0) return 0;

        int d1 = 0, d2 = 0;

        d1 = nums[0];

        if (nums.length == 1) return d1;

        d2 = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; ++i) {

            int temp = d2;
            d2 = Math.max(d1 + nums[i], d2);
            d1 = temp;
        }

        return d2;
    }
复制代码