題解 | #打家劫舍(一)#

---

題目鏈接

打家劫舍（一）

題目描述

描述

你是一個經(jīng)驗豐富的小偷，準備偷沿街的一排房間，每個房間都存有一定的現(xiàn)金，為了防止被發(fā)現(xiàn)，你不能偷相鄰的兩家，即，如果偷了第一家，就不能再偷第二家；如果偷了第二家，那么就不能偷第一家和第三家。
給定一個整數(shù)數(shù)組nums，數(shù)組中的元素表示每個房間存有的現(xiàn)金數(shù)額，請你計算在不被發(fā)現(xiàn)的前提下最多的偷竊金額。

示例1

輸入：

[1,2,3,4]

返回值：

6

說明：

最優(yōu)方案是偷第 2，4 個房間

示例2

輸入：

[1,3,6]

返回值：

7

說明：

最優(yōu)方案是偷第 1，3個房間

示例3

輸入：

[2,10,5]

返回值：

10

說明：

最優(yōu)方案是偷第 2 個房間

---

解題思路

簡單dp，對于每個房間只有偷不偷兩種，你是一個小偷，你也不知道后面有多少。

當我們訪問房間i時，我們只有兩種選擇：偷i，并且拿起i-2及以前所有的財富；不偷i，拿起i-1及以前所有的財富。我們可以保證我們訪問第i間房間時，拿到的錢是最多的。

這就很好解決了，用一個數(shù)組存儲累加的數(shù)就好，最后最多的財富值就是數(shù)組最后一項的值。

---

題解

//打家劫舍（一）
function rob(nums) {// write code herelet stealList = [];let max = 0;stealList[0] = nums[0];stealList[1] = nums[0] > nums[1] ? nums[0] : nums[1];for (let i = 2; i < nums.length; i++) {let s = stealList[i - 2] + nums[i];if (stealList[i - 1] > s)s = stealList[i - 1];stealList[i] = s;}return stealList[nums.length - 1];
}
console.log(rob([1, 2, 3, 4]));
module.exports = {rob: rob
};

總結

以上是生活随笔為你收集整理的[JS][dp]题解 | #打家劫舍(一)#的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。