資訊專欄INFORMATION COLUMN
摘要：給定一個代表每個房屋存放金額的非負整數數組，計算你在不觸動警報裝置的情況下，今晚能夠偷竊到的最高金額。狀態表示表示偷竊號到號房間所能獲得的最高金額。下標均從開始打家劫舍我們已經知道了房間單排排列的狀態轉移方程，接下來思考房間環狀排列的做法。
你是一個專業的小偷，計劃偷竊沿街的房屋，每間房內都藏有一定的現金。這個地方所有的房屋都 圍成一圈 ，這意味著第一個房屋和最后一個房屋是緊挨著的。同時，相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警 。
給定一個代表每個房屋存放金額的非負整數數組，計算你 在不觸動警報裝置的情況下 ，今晚能夠偷竊到的最高金額。
示例 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給定一個代表金額的非負整數數組nums，相鄰房間不可偷并且房間是圍成一圈的，讓我們輸出可以偷竊到的最高金額。
樣例：
如樣例所示，nums = [1,2,3,1]，偷竊1，3，號房間可以獲得最高金額4。
打家劫舍 I
我們先來看看「198. 打家劫舍」房間單排排列的動態規劃的做法。
狀態表示：f[i]表示偷竊1號到i號房間所能獲得的最高金額。那么，f[n]就表示偷竊1號到n號房間所能獲得的最高金額，即為答案。
狀態計算：
假設有i間房間，考慮最后一間偷還是不偷房間，有兩種選擇方案：
i-1間房間，不偷竊最后一間房間，那么問題就轉化為了偷竊1號到i- 1號房間所能獲得的最高金額，即f[i] = f[i-1]。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號到i - 1號房間所能獲得的最高金額。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是數組長度。需要對數組遍歷一次。
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]); }};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
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/120811.html
摘要：偷竊到的最高金額。世紀年代初美國數學家等人在研究多階段決策過程的優化問題時，提出了著名的最優化原理，把多階段過程轉化為一系列單階段問題，利用各階段之間的關系，逐個求解，創立了解決這類過程優化問題的新方法動態規劃。 showImg(https://segmentfault.com/img/bVbplM3?w=953&h=465); 題目描述 你是一個專業的小偷，計劃偷竊沿街的房屋，每間房...
摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...
摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區別...
摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。 這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。 在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...
摘要：字符數值例如，羅馬數字寫做，即為兩個并列的。通常情況下，羅馬數字中小的數字在大的數字的右邊。給定一個羅馬數字，將其轉換成整數。 Create by jsliang on 2019-05-23 13:24:24 Recently revised in 2019-05-23 14:55:20 一 目錄 不折騰的前端，和咸魚有什么區別 目錄 一 目錄 二 前言 三 解題 ...
閱讀 2114·2021-11-05 09:42
閱讀 2858·2021-09-23 11:21
閱讀 2853·2019-08-30 14:00
閱讀 3319·2019-08-30 13:15
閱讀 470·2019-08-29 17:18
閱讀 3558·2019-08-29 16:29
閱讀 2756·2019-08-29 14:06
閱讀 2803·2019-08-23 14:41
