本文主要是介绍动态规划专练( 231.打家劫舍Ⅱ),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
231.打家劫舍Ⅱ
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。
示例 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 <= nums.length <= 100
0 <= nums[i] <= 1000
题解:
本题在198.打家劫舍的基础上进行了变化,将首尾两个元素连成了环,成环之后思考的难度提高了很多,因为如过要使用动态规划的话,不知道从哪个位置开始。
因此第一步是将本题进行转换。首尾成环相较于没有成环,其实是多了三种情况。
- 情况一:我不考虑首尾元素,只考虑中间部分
- 情况二:我不考虑尾元素,只考虑首元素和中间部分
- 情况三:我不考虑首元素,只考虑中间部分和尾元素
在这三种情况中,其实情况一的值一定是小于等于情况二和情况三的。因为情况二和三考虑的范围包括住了情况一,在一个更大的范围内求解最大值,一定是大于等于的关系。
因此可以将情况二和情况三分别拆分成两个数组,送入到198.打家劫舍的算法中,再取最大值即可.
package com.offer;/*** @author bwzfy* @create 2024/4/16**/
public class _213打家劫舍Ⅱ {public static void main(String[] args) {System.out.println(rob(new int[]{2, 3, 2}));}public static int rob(int[] nums) {if (nums.length == 1) {return nums[0];}// 三种选择// 两头都不考虑(这种情况其实包含在了下面两种情况中,因此只要考虑下面两种情况下的最大值就可以了)// 只考虑头// 只考虑尾return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));}private static int rob(int[] nums, int left, int right) {if (right == left) {// 如果只有一个元素直接返回return nums[left];}int[] dp = new int[right - left + 1];// 只考虑一户人家的时候,最多能拿多少钱dp[0] = nums[left];// 只考虑两户人家的时候,最多能拿多少钱dp[1] = Math.max(nums[left], nums[left + 1]);for (int i = 2; i <= right - left; i++) {dp[i] = Math.max(dp[i - 1], nums[left + i] + dp[i - 2]);}return dp[right - left];}
}
这篇关于动态规划专练( 231.打家劫舍Ⅱ)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!