Open goldEli opened 5 years ago
分析:
对于每一栋别墅都有两种可能,偷,或者不偷,同时对应两个结果,偷后的总金额最大多少,不偷的总金额最大多少
假设偷和不偷对应的总净额分别为 r 和 nr:
第2栋房子: 偷:r = 1 不偷: nr = 0
第2栋房子: 偷:r = 2 不偷: nr = 1
.... 得到下表:
1 | 2 | 5 | 2 | 1 | 3 | |
r | 1 | 2 | 6 | 4 | 7 | 9 |
nr | 0 | 1 | 2 | 6 | 7 | 7 |
在比较 nr 和 r 的大小就可以得出,小偷可以偷到的最大金额为 9
转换成公式:
r[i] = nr[i-1] + currentNumber nr[i] = max(r[i-1], nr[i-1])
js代码:
cosnt robberNumber = (nums) => {
if (!nums || nums.length === 0) return 0
let r = 0
let nr = 0
let temp = 0
for (let i = 0; i < nums.length; ++i) {
temp = nr
nr = Math.max(r, nr)
r = temp + nums[i]
}
return Math.max(r, nr)
}
robberNumber([1,2,5,2,1,3])
// ==> 9
问题【LeetCode 198】: 一个小偷准备去偷一排别墅,但是相邻两个别墅被偷了会触发报警,所以在不出发报警的前提下,如何偷到最多的钱。 用数组表示一排别墅,比如 [1,2,5,2,1,3], index 为0的别墅和 index 为1的别墅相邻,index 为0的别墅可偷的钱为1。 如果是 [1,2,5,2,1,3],小偷偷到最多的钱总和为:1+5+3 = 9