LeetCode
思路
动态规划
dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]。
这里 dp[i] = Math.max(dp[i - 1], dp[i-2] + nums[i])
的逻辑是:到第 i 个房屋能偷窃的最大值,是两种情况的较大值:
- 一种情况是不偷第 i 个房屋,那么最大值就是到第 i-1 个房屋为止能偷窃的最大值,即
dp[i - 1]
; - 另一种情况是偷第 i 个房屋,那么就不能偷第 i-1 个房屋,所以最大值是当前房屋的值
nums[i]
加上到第 i-2 个房屋为止能偷窃的最大值,即dp[i - 2] + nums[i]
。
PS. dp[i]
定义
如果看到一些解读下的 dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1])
这样的解答, 那么这里的 i 实际上是表示第i+1
个房屋 因为他的数组 dp 实际上长度是 nums.length+1
,并且 dp[0] = 0
, dp[1] = nums[0].
题解
typescript
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function(nums) {
let dp = [nums[0], Math.max(nums[0], nums[1])]
// 1. 确定dp[i]数组及下标含义
// 2. 确定递推公式
// dp[i] = max(dp[i-2] + nums[i], dp[i - 1])
// 3. 递推初始化
// dp[0] = nums[0]
// dp[1] = Math.max(nums[0], nums[1])
// 4. 确定遍历顺序,dp[i]是前面两个递推来的,从前往后遍历
for(let i = 2; i < nums.length; i++){
dp[i] = Math.max(dp[i - 1], dp[i-2] + nums[i])
}
return dp[nums.length - 1]
};
空间优化 用两个变量来存。
typescript
var rob = function(nums) {
if(nums.length == 0) return 0;
if(nums.length == 1) return nums[0];
// 用两个指针做空间优化
let pre= nums[0]
let cur = Math.max(nums[0], nums[1])
for(let i = 2; i < nums.length; i++){
let tmp = cur;
cur = Math.max(pre + nums[i], cur);
pre = tmp;
}
return cur;
};