河南网站备案地址,南通网站建设方案,数字火币交易网站开发,做国外网站关键词用写#x1f4d1;前言
本文主要是【动态规划】——打家劫舍(java版)的文章#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ #x1f3ac;作者简介#xff1a;大家好#xff0c;我是听风与他#x1f947; ☁️博客首页#xff1a;CSDN主页听风与他 #x1f304;每日一…前言
本文主要是【动态规划】——打家劫舍(java版)的文章如果有什么需要改进的地方还请大佬指出⛺️ 作者简介大家好我是听风与他 ☁️博客首页CSDN主页听风与他 每日一句狠狠沉淀顶峰相见 目录 前言打家劫舍(java版)[LCR 089. 打家劫舍](https://leetcode.cn/problems/Gu0c2T/)代码:[LCR 090. 打家劫舍 II](https://leetcode.cn/problems/PzWKhm/)代码:文章末尾 打家劫舍(java版)
LCR 089. 打家劫舍
一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组 nums 请计算 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。
示例 1
输入nums [1,2,3,1]
输出4
解释偷窃 1 号房屋 (金额 1) 然后偷窃 3 号房屋 (金额 3)。偷窃到的最高金额 1 3 4 。示例 2
输入nums [2,7,9,3,1]
输出12
解释偷窃 1 号房屋 (金额 2), 偷窃 3 号房屋 (金额 9)接着偷窃 5 号房屋 (金额 1)。偷窃到的最高金额 2 9 1 12 。代码: public static int rob(int[] nums) {int n nums.length;//创建dp数组int dp[] new int[n];if(n1) {return nums[0];}//对dp[0],dp[1]的状态进行初始化dp[0]nums[0];dp[1]Math.max(nums[0], nums[1]);//从第三项开始进行动态规划要么取前i-1项要么取前i-2项加上nums[i]因为不能取相邻的两家不然会触发警报for(int i2;in;i) {dp[i]Math.max(dp[i-1], dp[i-2]nums[i]);}return dp[n-1];}LCR 090. 打家劫舍 II
一个专业的小偷计划偷窃一个环形街道上沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组 nums 请计算 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。
示例 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 [0]
输出0代码: public static int rob(int[] nums) {int n nums.length;if(n1) return nums[0];int dp1[] new int[n];//要头不要尾int dp2[] new int[n];//不要头要尾//对dp1和dp2进行初始化处理。dp1[0]nums[0];dp1[1]Math.max(nums[0], nums[1]);dp2[1]nums[1];//进行动态规划for(int i2;in;i) {dp1[i]Math.max(dp1[i-1], dp1[i-2]nums[i]);dp2[i]Math.max(dp2[i-1], dp2[i-2]nums[i]);}return Math.max(dp1[n-2], dp2[n-1]);}文章末尾
