39 lines
929 B
JavaScript
39 lines
929 B
JavaScript
/**
|
||
* @param {number[]} nums
|
||
* @return {number}
|
||
*/
|
||
const rob = function (nums) {
|
||
|
||
};
|
||
|
||
/*
|
||
设dp[i]为偷取第i家时获取的最大利润，那么dp[i]可以由两种情况得来
|
||
1.偷第i家，如果偷第i家，那么最大利润为 dp[i] = dp[i-2] + 第i家拥有的金额
|
||
2.不偷第i家，如果不偷第i家，那么最大利润为 dp[i-1]的最大利润
|
||
那么只需比较上面两种情况谁大，就是dp[i]的值，即dp[i] = Max(dp[i-1], dp[i-2] + nums[i])
|
||
*/
|
||
function f1(nums) {
|
||
const n = nums.length;
|
||
const dp = Array(n);
|
||
dp[0] = nums[0];
|
||
dp[1] = Math.max(nums[0], nums[1]);
|
||
for (let i = 2; i < dp.length; i++) {
|
||
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
|
||
}
|
||
return dp[n - 1];
|
||
}
|
||
|
||
/*
|
||
使用双指针优化
|
||
*/
|
||
function f2(nums) {
|
||
let prev = 0;
|
||
let curr = 0;
|
||
for (const num of nums) {
|
||
const temp = Math.max(curr, prev + num);
|
||
prev = curr;
|
||
curr = temp;
|
||
}
|
||
return curr;
|
||
}
|