专栏首页健程之道力扣198——打家劫舍

力扣198——打家劫舍

这次准备连讲三道题,这道题就是最基础的,利用动态规划可以解决。

原题

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

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

示例 :

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

原题url:https://leetcode-cn.com/problems/house-robber/

解题

动态规划-自顶向下

动态规划大家应该很容易就想到,如果偷了当前的金钱,下一家就不能偷,如果不偷当前的金钱,可以考虑下一家。比如:

小偷到了第3家,他有两个选择:不偷第3家之后去第4家、偷完第3家之后去第5家。这时他需要比较的是:

  • 从第4家开始能偷到的最多金钱
  • 第3家的金钱加上从第5家开始能偷到的最多金钱 上面两者谁更多,就选择怎么做。

那主要目的就是要求出从当前到结尾可以偷到的最大值,为了不重复计算,可以利用一个数组记录中间结果。

接下来看看代码:

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

        // 存储中间结果
        int[] result = new int[nums.length];
        Arrays.fill(result, -1);
        // 动态规划,利用中间结果,寻找最大值
        dp(0, nums, result);
        return result[0];
    }

    public int dp(int start, int[] nums, int[] result) {
        if (start >= nums.length) {
            return 0;
        }

        if (result[start] != -1) {
            return result[start];
        }

        result[start] = Math.max(
            // 选择偷当前的家
            nums[start] + dp(start + 2, nums, result),
            // 选择不偷当前的家
            dp(start + 1, nums, result)
        );

        return result[start];
    }
}

提交OK。

动态规划-自底向上

上面的写法其实是从头向尾考虑,写法上是递归。那么如果想不用递归呢?毕竟递归也是有缺陷的,如果次数过多,总调用栈就会很长。那我们来改造一下。

如果我们是从尾向头考虑呢?也就是从最后一家开始,选择偷或者不偷,最终到第一家。思想上还是很好理解的,和上面差不多,让我们看看代码:

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

        // 存储中间结果
        int[] result = new int[nums.length + 2];
        // 动态规划,利用中间结果,寻找最大值
        for (int i = nums.length - 1; i >= 0; i--) {
            result[i] = Math.max(
                // 当前不偷
                result[i + 1],
                // 当前偷
                nums[i] + result[i + 2]
            );
        }
        return result[0];
    }
}

提交也是OK的。

空间上的优化

我们仔细观察一下上面的写法,其实每次你利用到的中间状态只有两个,下一个位置和再下一个位置。那么此时我们也可以用三个变量来存储就够了,两个存储之后的值,还有一个存储当前的值。

让我们来看看代码:

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

        // 存储当前位置,下一个位置,和再下一个位置的结果
        int current = 0;
        int next_1 = 0;
        int next_2 = 0;
        // 动态规划,利用中间结果,寻找最大值
        for (int i = nums.length - 1; i >= 0; i--) {
            current = Math.max(
                // 当前不偷
                next_1,
                // 当前偷
                nums[i] + next_2
            );
            next_2 = next_1;
            next_1 = current;
        }
        return current;
    }
}

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题主要利用动态规划就可以解决,可以改写递归,优化空间复杂度。

本文分享自微信公众号 - 健程之道(JianJianCoder),作者:健健壮

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-01-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 力扣300——最长上升子序列

    这也是最基础的想法,利用递归,从每一个数开始,一个一个寻找,只要比选中的标准大,那么就以新的数为起点,继续找。全部找完后,找出最长的序列即可。

    健程之道
  • 力扣152——乘积最大子序列

    给定一个整数数组 nums ,找出一个序列中乘积最大的连续子序列(该序列至少包含一个数)。

    健程之道
  • 力扣416——分割等和子集

    这道题主要涉及的是动态规划,类似背包问题,主要还是需要找出状态转移方程,优化时可以考虑采用深度优先搜索。

    健程之道
  • leetcode哈希表之两数之和

    这里利用HashMap来存储目标值与当前值的差值及其索引,遍历nums数组,遇到存在的key则直接返回。

    codecraft
  • leetcode哈希表之两数之和

    这里利用HashMap来存储目标值与当前值的差值及其索引,遍历nums数组,遇到存在的key则直接返回。

    codecraft
  • 两数之和(TwoSum)

    我工作2年已经感觉到危机感,正准备同时这面临着两个问题了,不如蹭现在还有来得及一起去把算法练起来吧,光看可不行得练。尽可能的把 https://leetcode...

    爱敲代码的猫
  • TwoSum 相关问题思路总结

    TwoSum 作为 LeetCode 的第一题存在,想必大家应该对其并不陌生。如果仅仅是看这道题目本身,并不难,思想也特别的简单。

    五分钟学算法
  • TwoSum 相关问题思路总结

    TwoSum 作为 LeetCode 的第一题存在,想必大家应该对其并不陌生。如果仅仅是看这道题目本身,并不难,思想也特别的简单。

    帅地
  • Two Sum

    Given an array of integers, return indices of the two numbers such that they add...

    Tyan
  • 【leetcode刷题】T38-存在重复元素 III

    Given an array of integers, find out whether there are two distinct indices i an...

    木又AI帮

扫码关注云+社区

领取腾讯云代金券