C/C++教程

【LeetCode】213. 打家劫舍 II

本文主要是介绍【LeetCode】213. 打家劫舍 II,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

213. 打家劫舍 II

知识点:动态规划;打家劫舍

题目描述

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

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

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

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

输入:nums = [0]
输出:0

解法一:动态规划

此题和198题打家劫舍最大的区别就在于此题中所有的房子是连成一圈的,剩下的都一模一样。关键就在于从这个条件挖掘出信息,连成一圈,其实可以将其分解为两个子问题,意思就是说第一个房子和最后一个房子不能同时被偷,只能偷一个,所以可以将其分为一个是从0-n-1;一个是从1-n;然后就看两者谁大取谁;剩下的和198就一样了。

  • 1.确定dp数组和其下标的含义;dp[i]表示走到第i个房子前的偷到的最大金额;
  • 2.确定递推公式,即状态转移方程;小偷走到第i个房子面前有两种选择:偷或者不偷:1.偷:因为只能跨着房子偷,小偷想要偷第k个,那只能从第k-2个房子过来的,所以金额为dp[i-2]+nums[i];2.不偷:不偷是因为不能偷,因为已经偷过了第i-1房子了,再偷报警了,所以dp[i]=dp[i-1];最终的dp[i]就是两者中的大的。
  • 3.dp初始化;base case; dp[i]和前两个有关,所以遍历从2开始,dp[0]=nums[0],第一个房子肯定偷能到最大金额;dp[1]= Math.max(nums[0], nums[1]);只能偷一个房子,两间房子肯定偷金额大的那个;

优化:因为能偷的金额只和前两个状态有关,所以可以不用数组,只用两个变量记录就可以了,因为从左到右的过程中,偷到的总金额是单调不减的。所以可以这样操作。

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if(nums.length == 1) return nums[0];
        if(nums.length == 2) return Math.max(nums[0], nums[1]);
        return Math.max(rob(nums, 0, len-2), rob(nums, 1, len-1));
    }
    private int rob(int[] nums, int start, int end){
        int second = nums[start];
        int first = Math.max(nums[start], nums[start+1]);
        for(int i = start+2; i <= end; i++){
            int temp = first;
            first = Math.max(second+nums[i], first);
            second = temp;
        }
        return first;
    }
}
这篇关于【LeetCode】213. 打家劫舍 II的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!