[leetcode - Bliend-75 ] 198. House Robber (Medium)

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 不能取连续 index 的值，找到非连续 index 相加后最大的值。

Example

Input: nums = [1,2,3,1]
Output: 4
Explanation: 1(index-0) + 3(index-2) > 2(index-1) + 1(index-3)

Step

nums = [2] 则只有一个选项便是 2
nums = [2,7] 则有两个选项，第一个是去第一间拿到 1 块第二个是去第二间拿到 7 块，去第二间拿到的钱币较多所以放入 7，这时的 7 代表 nums = [1,7] 时可以拿到最多的钱
nums = [2,7,9] 有两个选项拿 9 和 7 之前的房子中最多钱的，因为 7 连着 9 所以要跳过 7 找 7 之前的最大值
不拿 9 而拿 9 之前的房子中最多钱的，而 9 之前最多钱的在 2 (nums = [2,7]) 已经算过并放进 dp 里面了

方法一和方法二的最大值放入 dp 中表示 nums = [2,7,9] 时可以拿得最多钱
nums = [2,7,9,3] 有两个选项拿 3 和 9 之前的房子 [2,7] 中最多钱的，因为 9 连着 3 所以要跳过 9 找 9 之前的最大值，而 9 之前的最大值在 2 (nums = [2,7]) 已经算过并放进 dp 里了
不拿 3 而拿 3 之前的房子 [2,7,9] 中最多钱的，而 3 之前最多钱的已经在 3 (nums = [2,7,9]) 中算过并放进 dp 中了

方法一和方法二的最大值放入 dp 中表示 nums = [2,7,9,3] 时可以拿得最多钱
nums = [2,7,9,3,1] 有两个选项拿 1 和 3 之前的房子 [2,7,9] 中最多钱的，因为 3 连着 1 所以要跳过 3 找 3 之前的最大值，而 3 之前的最大值在 3 (nums = [2,7,9]) 已经算过了并放进 dp 里了
不拿 1 而拿 1 之前的房子 [2,7,9,3] 中最多钱的，而 1 之前最多钱的已经在 4 (nums = [2,7,9,3] 中算过并放入 dp 中了

方法一和方法二的最大值放入 dp 中表示 nums = [2,7,9,3,1] 时可以拿得最多钱

Coding

/** * @param {number[]} nums * @return {number} */var rob = function(nums) {    if (nums.length === 0) return 0;    if (nums.length === 1) return nums[0];    if (nums.length === 2) return Math.max(nums[0], nums[1]);    const dp = [];    dp[0] = nums[0];    dp[1] = Math.max(nums[0], nums[1]);    for(let i = 2; i < nums.length; i++) {        dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);    }    return dp[dp.length - 1];};

Time complexity: O(n)