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

力扣213——打家劫舍 II

这一篇是上一篇的扩展,需要针对特殊情况特殊考虑,当然其本质还是动态规划。

原题

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

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

示例 1:

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。

示例 2:

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

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

解题

这道题的变化是,同样是一个数组,但是首尾相连了,也就是成了一个环,那么原本递推的方式也就行不通了,因为任何一个节点其实地位都相等了,也就找不到最初的状态,无法进行递推了。

但我们可以将现在的问题转化成我们已经解决的问题,仔细想想。所谓的首尾相连,针对状态进行划分,可以有三种情况:

  1. 首尾节点都不选择
  2. 只选择首节点,不选择尾结点
  3. 只选择尾结点,不选择首节点

因为我们最终是要求出最大值,那么只需要考虑后面两种情况,而这样的话,又可以转化成了原本的线性数组了。

接下来让我们看看代码:

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

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

        // 因为收尾相连,无法按照最初的动态规划来做,因为没有一个可以开始的点。
        // 那么就将未知问题转化为已知问题,针对首尾两个节点,可以有三种情况:
        // 1、首尾节点都不选择
        // 2、只选择首节点,不选择尾结点
        // 3、只选择尾结点,不选择首节点
        // 因为是要取最大值,且是非负整数数据,所以只考虑后两种情况

        return Math.max(
            // 只选择首节点,不选择尾结点
            calMax(nums, 0, nums.length - 2),
            // 只选择尾结点,不选择首节点
            calMax(nums, 1, nums.length - 1)
        );
    }

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

提交OK。

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题主要还是利用动态规划,只是需要大家进行思路转化,将未知转化为 已知,从而解决问题。

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 力扣416——分割等和子集

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

    健程之道
  • 剑指offer 33——二叉搜索树的后序遍历序列

    输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。

    健程之道
  • 力扣560——和为K的子数组

    给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。

    健程之道
  • Move Zeroes

    Tyan
  • 【算法随记七】巧用SIMD指令实现急速的字节流按位反转算法。

      字节按位反转算法,在有些算法加密或者一些特殊的场合有着较为重要的应用,其速度也是一个非常关键的应用,比如一个byte变量a = 3,其二进制表示为00000...

    用户1138785
  • Go语言排序与接口实例分析

    本文实例讲述了Go语言排序与接口用法。分享给大家供大家参考。具体如下: import "fmt" type Sorter interface { Len()...

    李海彬
  • leetcode-594-Longest Harmonious Subsequence

    chenjx85
  • 几种排序算法

    通常堆是通过一维数组来实现的。在阵列起始位置为0的情况中 (1)父节点i的左子节点在位置(2i+1); (2)父节点i的右子节点在位置(2i+2); (3)子节...

    用户1637228
  • 基础练习 数列排序

      第一行为一个整数n。   第二行包含n个整数,为待排序的数,每个整数的绝对值小于10000。

    刘开心_1266679
  • MySQL NDB Cluster介绍

    最近翻译了好几篇关于NDB的文章,相信有很多人会有疑问,NDB Cluster究竟是个什么东西?它是一款新产品吗?它和InnoDB Cluster有什么不同?它...

    MySQLSE

扫码关注云+社区

领取腾讯云代金券