目錄
- 1、題目
- 2、思路
- 3、c++代碼
- 4、java代碼
1、題目
你是一個專業的小偷，計劃偷竊沿街的房屋，每間房內都藏有一定的現金，這個地方所有的房屋都 圍成一圈 ，這意味著第一個房屋和最后一個房屋是緊挨著的，同時，相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警 ，
給定一個代表每個房屋存放金額的非負整數陣列，計算你 在不觸動警報裝置的情況下 ，今晚能夠偷竊到的最高金額，
示例 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
2、思路
給定一個代表金額的非負整數陣列nums，相鄰房間不可偷并且房間是圍成一圈的，讓我們輸出可以偷竊到的最高金額，
樣例：
如樣例所示，nums = [1,2,3,1]，偷竊1，3，號房間可以獲得最高金額4，
打家劫舍 I
我們先來看看「198. 打家劫舍」房間單排排列的動態規劃的做法，
狀態表示：f[i]表示偷竊1號到i號房間所能獲得的最高金額，那么，f[n]就表示偷竊1號到n號房間所能獲得的最高金額，即為答案，
狀態計算：
假設有i間房間，考慮最后一間偷還是不偷房間，有兩種選擇方案：
- 1、偷竊前
i-1間房間，不偷竊最后一間房間，那么問題就轉化為了偷竊1號到i- 1號房間所能獲得的最高金額，即f[i] = f[i-1]，
- 2、偷竊前
i - 2間房間和最后一間房間 (相鄰的房屋不可闖入)，那么問題就轉化為了偷竊1號到i- 2號房間所能獲得的最高金額再加上偷竊第i號房間的金額，即f[i] = f[i - 2] + nums[i]， (下標均從1開始)
兩種方案，選擇其中金額最大的一個，因此狀態轉移方程為： f[i] = max(f[i - 1], f[i - 2] + nums[i])， (下標均從1開始)
打家劫舍 II
我們已經知道了房間單排排列的狀態轉移方程，接下來思考房間環狀排列的做法，
房間環狀排列 意味著第一間和最后一間不能同時選擇，因此我們可以分成兩種情況來討論：
- 1、不偷竊最后一間房間，那么問題轉化為偷竊
1號到i - 1號房間所能獲得的最高金額， - 2、不偷竊第一間房間，那么問題轉化為偷竊
2號到i號房間所能獲得的最高金額，
兩種情況中取最大值，這樣我們就把環狀排列問題轉化為了兩個單排排列的子問題，
我們定義兩個陣列f[]和g[]，分別用f[n-1]和g[n]兩個陣列值來表示區間[1, n - 1]和[2, n]的最大金額值，圖示程序如下：
初始化：
f[1] = nums[0]，只偷竊1號房間所能獲得的最高金額為nums[0]，
g[2] = nums[1]，把第二間房間當成房間單排排列的起點，只偷竊2號房間所能獲得的最高金額為nums[1]，
實作細節：
我們定義的狀態表示f[]、g[]陣列以及nums[]陣列下標均是從1開始的，而題目給出的nums[]陣列下標是從0開始的，為了一 一對應，狀態轉移方程中的nums[i]的值要往前錯一位，取nums[i - 1]，這點細節希望大家可以注意一下，
時間復雜度分析： O ( n ) O(n) O(n)，其中 n n n是陣列長度，需要對陣列遍歷一次，
3、c++代碼
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if(n == 1) return nums[0]; //只有一間房間，回傳nums[0]
vector<int>f(n + 1), g(n + 1);
f[1] = nums[0], g[2] = nums[1]; //初始化
for(int i = 2; i <= n - 1; i++) f[i] = max(f[i - 1], f[i - 2] + nums[i - 1]); //區間[1,n-1]最大值
for(int i = 3; i <= n; i++) g[i] = max(g[i - 1], g[i - 2] + nums[i - 1]); //區間[2,n]最大值
return max(f[n - 1], g[n]);
}
};
4、java代碼
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if(n == 1) return nums[0]; //只有一間房間，回傳nums[0]
int[] f = new int[n + 1], g = new int[n + 1];
f[1] = nums[0]; //初始化
g[2] = nums[1];
for(int i = 2; i <= n - 1; i++) f[i] = Math.max(f[i - 1], f[i - 2] + nums[i - 1]);
for(int i = 3; i <= n; i++) g[i] = Math.max(g[i - 1], g[i - 2] + nums[i - 1]);
return Math.max(f[n - 1], g[n]);
}
}
原題鏈接：213. 打家劫舍 II
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/301954.html
標籤：java
上一篇：Spring原理篇(7)--Spring最經常使用的一個功能 依賴注入, 該功能原始碼是一定需要知道的；這是我們日常開發中的核心； 了解其原始碼；這一篇就夠了；