继续创作，加快生长！这是我参加「日新方案 10 月更文应战」的第18天，点击检查活动概况

打家劫舍1

标题

你是一个专业的小偷，方案偷盗沿街的房子。每间房内都藏有必定的现金，影响你偷盗的仅有限制要素便是相邻的房子装有彼此连通的防盗体系，假如两间相邻的房子在同一晚上被小偷闯入，体系会自动报警。

给定一个代表每个房子存放金额的非负整数数组，核算你 不牵动警报设备的状况下 ，一夜之内能够偷盗到的最高金额。

示例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 。

解题思路

打家劫舍的问题是用动态规划解决的经典问题。

首要第一步：确认 dp 数组以及下标的含义，dp[i]：考虑下标i（包括i）以内的房子，最多能够偷盗的金额为dp[i]。

第二步确认递推公式：
假如偷第i房间，那么dp[i] = dp[i – 2] + nums[i]，由于不能再考虑第i-1间房，所以最多能够偷盗的金额为dp[i-2] 加上第i房间偷到的钱。

假如不偷第i房间，那么dp[i] = dp[i – 1]。

然后dp[i]取最大值，即dp[i] = max(dp[i – 2] + nums[i], dp[i – 1]);

第三步，dp 数组初始化：从dp[i]的界说上来讲，dp[0] 必定是 nums[0]，dp[1]便是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1]);

第四步，确认遍历顺序：dp[i] 是依据dp[i – 2] 和 dp[i – 1] 推导出来的，那么必定是早年到后遍历！

代码完成

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if(length == 1){
            return nums[0];
        }
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
        }
        return dp[length - 1];
    }
}

复杂度剖析

  • 时间复杂度：O(n)，其间 n 是数组长度。只需要对数组遍历一次。

  • 空间复杂度：O(1)。

打家劫舍2

标题

你是一个专业的小偷，方案偷盗沿街的房子，每间房内都藏有必定的现金。这个当地一切的房子都 围成一圈 ，这意味着第一个房子和最终一个房子是紧挨着的。同时，相邻的房子装有彼此连通的防盗体系，假如两间相邻的房子在同一晚上被小偷闯入，体系会自动报警 。

给定一个代表每个房子存放金额的非负整数数组，核算你 在不牵动警报设备的状况下 ，今晚能够偷盗到的最高金额。

示例1：

输入：nums = [2,3,2]
输出：3
解说：你不能先偷盗 1 号房子（金额 = 2），然后偷盗 3 号房子（金额 = 2）, 由于他们是相邻的。

示例2：

输入：nums = [1,2,3,1]
输出：4
解说：你能够先偷盗 1 号房子（金额 = 1），然后偷盗 3 号房子（金额 = 3）。
偷盗到的最高金额 = 1 + 3 = 4 。

示例3：

输入：nums = [1,2,3]
输出：3

解题思路

之前咱们现已做过一道打家劫舍的标题了，利用动态规划能够求解，本题与之前的标题仅有的差异在于成环了。

对于数组，成环主要有以下三种状况：

状况一：考虑不包括首尾元素
例如，数组 [1,6,1,9,1], 咱们考虑的状况便是下标从1~3的状况，也便是[6,1,9];

状况二：考虑包括首元素，不包括尾元素
例如，数组 [1,6,1,9,1], 咱们考虑的状况便是下标从0~3的状况，也便是[1,6,1,9];

状况三：考虑包括尾元素，不包括首元素
例如，数组 [1,6,1,9,1], 咱们考虑的状况便是下标从1~4的状况，也便是[6,1,9,1];

由于状况一现已被状况二和三所包括，所以咱们在求解的时候，只需要包括后俩种状况即可。

代码完成

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];
        // 包括首元素，不包括尾元素
        int value1 = RobRange(nums, 0, nums.length-2);
        // 包括尾元素，不包括首元素
        int value2 = RobRange(nums, 1, nums.length-1);
        return Math.max(value1, value2);
    }
    public int RobRange(int[] nums, int start, int end){
        if(start == end) return nums[start];
        int[] dp = new int[nums.length];
        dp[start] = nums[start];
        dp[start + 1] = Math.max(nums[start], nums[start+1]);
        for(int i = start + 2; i <= end; i++){
            dp[i] = Math.max(dp[i-2]+nums[i], dp[i - 1]);
        }
        return dp[end];
    }
}

复杂度剖析

  • 时间复杂度：O(n)，其间 n 是数组长度。
  • 空间复杂度：O(1)。

我是杰少，假如您觉的我写的不错，那请给我 点赞+谈论+保藏 后再走哦！

往期文章：

  • 运用 Google Breakpad 来助力解决程序溃散
  • UE4 多人游戏服务器探究
  • 运用虚幻引擎自动化东西完成自动化布置
  • 怎么在 UE4 中制作一扇自动敞开的大门
  • 怎么在 UE4 顶用代码去控制人物移动
  • 怎么给 UE4 场景增加游戏人物
  • UE4：Android 渠道开发实践攻略
  • UE4 开发避坑攻略（继续更新）
  • 新年开工啦，放个小焰火庆祝一下
  • 聊聊与苹果审核员的爱恨情仇(下)
  • 聊聊与苹果审核员的爱恨情仇(上)
  • 一名普通东西人的 2021 | 2021年终总结
  • 二叉树刷题总结：二叉搜索树的特点
  • 二叉树总结：二叉树的特点
  • 二叉树总结：二叉树的修正与结构
  • StoreKit2 有这么香？嗯，我试过了，真香
  • 看完这篇文章，再也不怕面试官问我怎么结构二叉树啦！
  • 那帮做游戏的又想让我们氪金，太坏了！
  • 手把手带你撸一个网易云音乐主页 | 适配篇
  • 手把手带你撸一个网易云音乐主页（三）
  • 手把手带你撸一个网易云音乐主页（二）
  • 手把手带你撸一个网易云音乐主页（一）
  • 代码要写注释吗？写你就输了
  • Codable发布这么久我就不学，摸鱼爽歪歪，哎~便是玩儿
  • iOS 优雅的处理网络数据，你真的会吗？不如看看这篇
  • UICollectionView 自界说布局！看这篇就够了

请你喝杯 ☕️ 点赞 + 重视哦～

  1. 阅读完记住给我点个赞哦，有 有动力
  2. 重视大众号— HelloWorld杰少，第一时间推送新姿势

最终，创作不易，假如对我们有所帮助，希望我们点赞支撑，有什么问题也能够在谈论区里评论～**