[LeetCode] 198. House Robber 刷題筆記
Cathy P
 2022-03-19 23:12:13      

題目

LeetCode 連結：
https://leetcode.com/problems/house-robber/

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

你是一個小偷。你打算偷一整條街的房子。每一間房子都有錢可以偷，但如果偷了兩間相鄰的房子，就會觸發警報系統引來警察，導致你被逮補。

題目會提供一個數字 array，array 的值代表每一間房子可以偷盜的錢，在
不驚動警報系統的前提，要怎麼偷才能偷到最多的錢呢？

Example 1:

1
2
3
Input: nums = [1,2,3,1]
Output: 4
Explanation: 1 + 3 = 4.

Example 2:

1
2
3
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: 2 + 9 + 1 = 12.

解題過程

  1. 陣列 nums 紀錄每個房子的錢，我們還需要一個紀錄一個目前房子可以偷到的最大值的陣列 m。
  2. 只有第一間房子的時候，只有第一間可以偷。所以最大值 m[0] 為 nums[0]。
  3. 當有兩間房子的時候，因為不能偷相鄰的房子，兩間挑一間比較多錢的偷。m[1] = Max(nums[0],nums[1])。
  4. 當有 n 間房子的時候，若選擇了這間房子，則不能去偷上一間房子，所以要在「上一間房子的最大值」和「上上間房子的最大值+這間房子」取大值。Max(m[n-1], m[n-2]+nums[n])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {

    // 1. 陣列 nums 紀錄每個房子的錢，我們還需要一個紀錄一個目前房子可以偷到的最大值的陣列 m。
    let maxs = [];

    // 2. 只有第一間房子的時候，只有第一間可以偷。。
    // 3. 當有兩間房子的時候，因為不能偷相鄰的房子，兩間挑一間比較多錢的偷。
    maxs[0] = nums[0];
    maxs[1] = Math.max(nums[0], nums[1]);

    // 當有 n 間房子的時候，若選擇了這間房子，則不能去偷上一間房子，
    // 所以要在「上一間房子的最大值」和「上上間房子的最大值+這間房子」取大值。
    for(let i=2; i<nums.length; i++){
        maxs[i] = Math.max(maxs[i-1], maxs[i-2]+nums[i]);
    }
    return maxs[maxs.length-1];
};