摘要:偷竊到的最高金額。世紀(jì)年代初美國(guó)數(shù)學(xué)家等人在研究多階段決策過程的優(yōu)化問題時(shí),提出了著名的最優(yōu)化原理,把多階段過程轉(zhuǎn)化為一系列單階段問題,利用各階段之間的關(guān)系,逐個(gè)求解,創(chuàng)立了解決這類過程優(yōu)化問題的新方法動(dòng)態(tài)規(guī)劃。
題目描述
你是一個(gè)專業(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:
輸入: [2,3,2]
輸出: 3
解釋: 你不能先偷竊 1 號(hào)房屋(金額 = 2),然后偷竊 3 號(hào)房屋(金額 = 2), 因?yàn)樗麄兪窍噜彽摹?br>示例 2:
輸入: [1,2,3,1]
輸出: 4
解釋: 你可以先偷竊 1 號(hào)房屋(金額 = 1),然后偷竊 3 號(hào)房屋(金額 = 3)。
偷竊到的最高金額 = 1 + 3 = 4 。
此題為典型的動(dòng)態(tài)規(guī)劃問題,但是我們需要考慮幾種特殊情況
此題為一個(gè)環(huán),所以兩端不可并行探索,所以分為兩種情況,
第一種 探索 0 - (length - 2)
第二種 探索 1 - (length - 1)
在考慮只有長(zhǎng)度為1或2的時(shí)候
綜合考慮
先放出所有代碼
</>復(fù)制代碼
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function(nums) {
//特殊情況
const len = nums.length
if (len === 0) return 0
if (len === 1) return nums[0]
if (len === 2) return Math.max(nums[0], nums[1])
const rob = function(nums, start, end) {
let pMax = nums[start]
let cMax = Math.max(pMax, nums[start + 1])
for (let i = start + 2; i <= end; i++) {
console.log(i,cMax,pMax)
let tmp = cMax
cMax = Math.max((pMax +nums[i]), cMax)
pMax = tmp
}
return cMax
}
return Math.max(rob(nums, 0, len-2), rob(nums, 1, len-1))
};
</>復(fù)制代碼
動(dòng)態(tài)規(guī)劃函數(shù)為 rob
詳細(xì)解析下rob
先科普下動(dòng)態(tài)規(guī)劃思想
</>復(fù)制代碼
動(dòng)態(tài)規(guī)劃(dynamic programming)是運(yùn)籌學(xué)的一個(gè)分支,是求解決策過程(decision process)最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國(guó)數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過程(multistep decision process)的優(yōu)化問題時(shí),提出了著名的最優(yōu)化原理(principle of optimality),把多階段過程轉(zhuǎn)化為一系列單階段問題,利用各階段之間的關(guān)系,逐個(gè)求解,創(chuàng)立了解決這類過程優(yōu)化問題的新方法——?jiǎng)討B(tài)規(guī)劃。1957年出版了他的名著《Dynamic Programming》,這是該領(lǐng)域的第一本著作。
簡(jiǎn)單來說,動(dòng)態(tài)規(guī)劃就是尋找每個(gè)階段的最優(yōu)解
那我們先按照第一種情況分析下(從0 到 length - 2)
假設(shè)我們進(jìn)行測(cè)試的數(shù)組為
[3,1,5,12,6,8,13,2]
那我們探索
首先我們進(jìn)行前兩個(gè)的探索,然后每加一個(gè)數(shù),進(jìn)行兩種情況的比較,選出局部最優(yōu)解
【3,1】最優(yōu)解為3 前最優(yōu)解為3
【3,1,5】最優(yōu)解為8 前最優(yōu)解為3 【3 + 5】
【3,1,5,12】最優(yōu)解為 3 + 12 = 15 > 8 最優(yōu)解為 【3 + 12】前最優(yōu)解為8
【3,1,5,12,6】最有解為 15 > 8 + 6 最優(yōu)解為 【3 + 12】前最優(yōu)解為 15
【3,1,5,12,6,8】最優(yōu)解為 15 + 8 > 15 最優(yōu)解為 【3 + 12 + 8】為23 前最優(yōu)解為15
【3,1,5,12,6,8,13】最優(yōu)解為 15 + 13 > 23 最優(yōu)解為 【3 + 12 + 13】前最優(yōu)解為23
【3,1,5,12,6,8,13,2】最優(yōu)解為 28 > 23 + 2 最優(yōu)解為 【3 + 12 + 13】
依次類推 保證每個(gè)階段都有最優(yōu)解
最終提交
通過
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/102388.html
摘要:給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組,計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下,今晚能夠偷竊到的最高金額。狀態(tài)表示表示偷竊號(hào)到號(hào)房間所能獲得的最高金額。下標(biāo)均從開始打家劫舍我們已經(jīng)知道了房間單排排列的狀態(tài)轉(zhuǎn)移方程,接下來思考房間環(huán)狀排列的做法。 ...
摘要:微信公眾號(hào)記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會(huì)根據(jù)題解以及留言內(nèi)容,進(jìn)行補(bǔ)充,并添加上提供題解的小伙伴的昵稱和地址。本許可協(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 題。 一 目錄 不折騰的前端,和咸魚有什么區(qū)別...
摘要:在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起,每天更新一題,順序從易到難,目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目,語言 JavaScript。 在線網(wǎng)站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公眾號(hào): showImg(htt...
摘要:你是一個(gè)專業(yè)的小偷,計(jì)劃偷竊沿街的房屋。給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組,計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下,能夠偷竊到的最高金額。示例輸入輸出解釋偷竊號(hào)房屋金額,然后偷竊號(hào)房屋金額。偷竊到的最高金額。 你是一個(gè)專業(yè)的小偷,計(jì)劃偷竊沿街的房屋。每間房?jī)?nèi)都藏有一定的現(xiàn)金,影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng),如果兩間相鄰的房屋在同一晚上被小偷闖入,系統(tǒng)會(huì)自動(dòng)...
閱讀 1137·2021-08-12 13:24
閱讀 2985·2019-08-30 14:16
閱讀 3309·2019-08-30 13:01
閱讀 2072·2019-08-30 11:03
閱讀 2773·2019-08-28 17:53
閱讀 3088·2019-08-26 13:50
閱讀 2268·2019-08-26 12:00
閱讀 948·2019-08-26 10:38