資訊專(zhuān)欄INFORMATION COLUMN
摘要：給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下，今晚能夠偷竊到的最高金額。狀態(tài)表示表示偷竊號(hào)到號(hào)房間所能獲得的最高金額。下標(biāo)均從開(kāi)始打家劫舍我們已經(jīng)知道了房間單排排列的狀態(tài)轉(zhuǎn)移方程，接下來(lái)思考房間環(huán)狀排列的做法。
你是一個(gè)專(zhuān)業(yè)的小偷，計(jì)劃偷竊沿街的房屋，每間房?jī)?nèi)都藏有一定的現(xiàn)金。這個(gè)地方所有的房屋都 圍成一圈 ，這意味著第一個(gè)房屋和最后一個(gè)房屋是緊挨著的。同時(shí)，相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警 。
給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你 在不觸動(dòng)警報(bào)裝置的情況下 ，今晚能夠偷竊到的最高金額。
示例 1：
輸入：nums = [2,3,2]輸出：3解釋?zhuān)耗悴荒芟韧蹈` 1 號(hào)房屋（金額 = 2），然后偷竊 3 號(hào)房屋（金額 = 2）, 因?yàn)樗麄兪窍噜彽摹?/code>示例 2：
輸入：nums = [1,2,3,1]輸出：4解釋?zhuān)耗憧梢韵韧蹈` 1 號(hào)房屋（金額 = 1），然后偷竊 3 號(hào)房屋（金額 = 3）。 偷竊到的最高金額 = 1 + 3 = 4 。示例 3：
輸入：nums = [0]輸出：0給定一個(gè)代表金額的非負(fù)整數(shù)數(shù)組nums，相鄰房間不可偷并且房間是圍成一圈的，讓我們輸出可以偷竊到的最高金額。
樣例：
如樣例所示，nums = [1,2,3,1]，偷竊1，3，號(hào)房間可以獲得最高金額4。
打家劫舍 I
我們先來(lái)看看「198. 打家劫舍」房間單排排列的動(dòng)態(tài)規(guī)劃的做法。
狀態(tài)表示：f[i]表示偷竊1號(hào)到i號(hào)房間所能獲得的最高金額。那么，f[n]就表示偷竊1號(hào)到n號(hào)房間所能獲得的最高金額，即為答案。
狀態(tài)計(jì)算：
假設(shè)有i間房間，考慮最后一間偷還是不偷房間，有兩種選擇方案：
i-1間房間，不偷竊最后一間房間，那么問(wèn)題就轉(zhuǎn)化為了偷竊1號(hào)到i- 1號(hào)房間所能獲得的最高金額，即f[i] = f[i-1]。i - 2間房間和最后一間房間 (相鄰的房屋不可闖入)，那么問(wèn)題就轉(zhuǎn)化為了偷竊1號(hào)到i- 2號(hào)房間所能獲得的最高金額再加上偷竊第i號(hào)房間的金額，即f[i] = f[i - 2] + nums[i]。 (下標(biāo)均從1開(kāi)始)兩種方案，選擇其中金額最大的一個(gè)。因此狀態(tài)轉(zhuǎn)移方程為： f[i] = max(f[i - 1], f[i - 2] + nums[i])。 (下標(biāo)均從1開(kāi)始)
打家劫舍 II
我們已經(jīng)知道了房間單排排列的狀態(tài)轉(zhuǎn)移方程，接下來(lái)思考房間環(huán)狀排列的做法。
房間環(huán)狀排列 意味著第一間和最后一間不能同時(shí)選擇，因此我們可以分成兩種情況來(lái)討論：
1號(hào)到i - 1號(hào)房間所能獲得的最高金額。2號(hào)到i號(hào)房間所能獲得的最高金額。兩種情況中取最大值，這樣我們就把環(huán)狀排列問(wèn)題轉(zhuǎn)化為了兩個(gè)單排排列的子問(wèn)題。
我們定義兩個(gè)數(shù)組f[]和g[]，分別用f[n-1]和g[n]兩個(gè)數(shù)組值來(lái)表示區(qū)間[1, n - 1]和[2, n]的最大金額值，圖示過(guò)程如下：
初始化：
f[1] = nums[0]，只偷竊1號(hào)房間所能獲得的最高金額為nums[0]。
g[2] = nums[1]，把第二間房間當(dāng)成房間單排排列的起點(diǎn)，只偷竊2號(hào)房間所能獲得的最高金額為nums[1]。
實(shí)現(xiàn)細(xì)節(jié)：
我們定義的狀態(tài)表示f[]、g[]數(shù)組以及nums[]數(shù)組下標(biāo)均是從1開(kāi)始的，而題目給出的nums[]數(shù)組下標(biāo)是從0開(kāi)始的。為了一 一對(duì)應(yīng)，狀態(tài)轉(zhuǎn)移方程中的nums[i]的值要往前錯(cuò)一位，取nums[i - 1]，這點(diǎn)細(xì)節(jié)希望大家可以注意一下。
時(shí)間復(fù)雜度分析： O ( n ) O(n) O(n)，其中 n n n是數(shù)組長(zhǎng)度。需要對(duì)數(shù)組遍歷一次。
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]); //區(qū)間[1,n-1]最大值 for(int i = 3; i <= n; i++) g[i] = max(g[i - 1], g[i - 2] + nums[i - 1]); //區(qū)間[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
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/120811.html
摘要：偷竊到的最高金額。世紀(jì)年代初美國(guó)數(shù)學(xué)家等人在研究多階段決策過(guò)程的優(yōu)化問(wèn)題時(shí)，提出了著名的最優(yōu)化原理，把多階段過(guò)程轉(zhuǎn)化為一系列單階段問(wèn)題，利用各階段之間的關(guān)系，逐個(gè)求解，創(chuàng)立了解決這類(lèi)過(guò)程優(yōu)化問(wèn)題的新方法動(dòng)態(tài)規(guī)劃。 showImg(https://segmentfault.com/img/bVbplM3?w=953&h=465); 題目描述 你是一個(gè)專(zhuān)業(yè)的小偷，計(jì)劃偷竊沿街的房屋，每間房...
摘要：微信公眾號(hào)記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會(huì)根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱(chēng)和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...
摘要：月下半旬攻略道題，目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚(yú)有什么區(qū)別...
摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
摘要：字符數(shù)值例如，羅馬數(shù)字寫(xiě)做，即為兩個(gè)并列的。通常情況下，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊。給定一個(gè)羅馬數(shù)字，將其轉(zhuǎn)換成整數(shù)。 Create by jsliang on 2019-05-23 13:24:24 Recently revised in 2019-05-23 14:55:20 一 目錄 不折騰的前端，和咸魚(yú)有什么區(qū)別 目錄 一 目錄 二 前言 三 解題 ...
閱讀 2106·2021-11-05 09:42
閱讀 2851·2021-09-23 11:21
閱讀 2840·2019-08-30 14:00
閱讀 3313·2019-08-30 13:15
閱讀 464·2019-08-29 17:18
閱讀 3546·2019-08-29 16:29
閱讀 2748·2019-08-29 14:06
閱讀 2793·2019-08-23 14:41
