day153-LeetCode 198. 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 system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
(大意是:求最大不连续的值)

分析

假设为[m0,m1,m2,m3,….],求最大的数

如果房子只有[m0], max = mo

[m0,m1], max = Max(m0,m1)

[m0,m1,m2], max = Max(m0+m2,m1)

题解

function robber (nums) {
let maxSum = new Array()
if(nums.length === 0) return 0
if(nums.length === 1) return nums[0]
if(nums.length === 2) return Math.max(nums[1],nums[0])

maxSum.push(nums[0])
maxSum.push(Math.max(nums[0],nums[1]))

for(let i = 2; i < nums.length; i++) {
// Max(m0+m2,m1),计算公式
maxSum[i] = Math.max(nums[i] + maxSum[i-2], maxSum[i-1])
}
return maxSum.pop()
}
文章作者: lmislm
文章链接: http://lmislm.com/2019/06/15/2019-06-15/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 LMISLMのBlog