题目描述(简单难度)

一个数组,每个元素代表商店的存款,一个小偷晚上去偷商店,问最多能偷多少钱。有一个前提,不能偷相邻的商店,不然警报会响起。

思路分析

一道很典型的通过子问题去解决原问题的题目,所以可以通过递归以及动态规划解决。

如果我们需要求前 n 家商店最多能偷多少钱,并且知道了前 n - 1 家店最多能偷的钱数,前 n - 2 家店最多能偷的钱数。

对于第 n 家店,我们只能选择偷或者不偷。

如果偷的话,那么前 n 家商店最多能偷的钱数就是「前 n - 2 家店最多能偷的钱数」加上「第 n 家店的钱数」。因为选择偷第 n 家商店,第 n - 1 家商店就不可以偷了。

如果不偷的话,那么前 n 家商店最多能偷的钱数就是「前 n - 1 家店最多能偷的钱数」。

最终前 n 家商店最多能偷的钱数就是上边两种情况选择较大的值。

接下来就是递归出口或者说初始条件。

n = 0,也就没有商店,那么能偷的最大钱数当然是 0 了。

n = 1,也就是只有一家店的时候,能偷的最大钱数就是当前店的钱数。

解法一 递归

通过上边的分析,代码也就直接出来了。

public int rob(int[] nums) {
    return robHelpler(nums, nums.length);
}

private int robHelpler(int[] nums, int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return nums[0];
    }
    return Math.max(robHelpler(nums, n - 2) + nums[n - 1], robHelpler(nums, n - 1));
}

然后就会意料之中的超时。

原因很简单,因为递归中会计算很多重复的解,解法方案的话我们就是把递归过程中的解存起来,第二次遇到的话直接返回即可。

public int rob(int[] nums) {
    int[] map = new int[nums.length + 1];
    Arrays.fill(map, -1);
    return robHelpler(nums, nums.length, map);
}

private int robHelpler(int[] nums, int n, int[] map) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return nums[0];
    }
    if (map[n] != -1) {
        return map[n];
    }
    int res = Math.max(robHelpler(nums, n - 2, map) + nums[n - 1], robHelpler(nums, n - 1, map));
    map[n] = res;
    return res;
}

解法二 动态规划

有了上边的递归和之前的分析,其实动态规划也可以直接出来了。

dp[n] 数组表示前 n 天能够带来的最大收益。

dp[n] = Math.max(dp[n - 2] + nums[n - 1], dp[n - 1] )

初始条件的话,

dp[0] = 0 以及 dp[1] = nums[0]

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

    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = nums[0];
    for (int i = 2; i <= n; i++) {
        dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
    }
    return dp[n];
}

接下来就是动态规划空间复杂度上的优化,比如 5题10题53题72题 115 题 等等都已经用过了。

原因就是我们更新 dp[i] 的时候,只需要 dp[i - 1] 以及 dp[i - 2] 的信息,再之前的信息就不需要了,所以我们不需要数组,只需要几个变量就可以了。

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

    int pre = 0; //代替上边代码中的 dp[i - 2]
    int cur = nums[0]; //代替上边代码中的 dp[i - 1] 和 dp[i]
    for (int i = 2; i <= n; i++) {
        int temp = cur;
        cur = Math.max(pre + nums[i - 1], cur);
        pre = temp;
    }
    return cur;
}

一道很典型的题,可以体会从递归 -> 递归加缓冲 -> 动态规划 -> 动态规划空间复杂度优化这一系列的过程,如果题目做的多了,最开始就可以直接想到最后的方法了。

results matching ""

    No results matching ""