打家劫舍(java版)

📑前言

本文主要是【動態規劃】——打家劫舍(java版)的文章，如果有什么需要改進的地方還請大佬指出??

🎬作者簡介：大家好，我是聽風與他🥇
??博客首頁：CSDN主頁聽風與他
🌄每日一句：狠狠沉淀，頂峰相見

打家劫舍(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(n==1) {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 i=2;i<n;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(n==1) 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 i=2;i<n;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]);}