题目
198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 400
我的代码（TypeScript）
function rob(nums: number[]): number {
if (nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
if (nums.length == 2) {
return Math.max(nums[0], nums[1]);
}
if (nums.length == 3) {
return Math.max(nums[0] + nums[2], nums[1]);
}
let t0: number = nums[0];
let t1: number = nums[1];
let t2: number = nums[0] + nums[2];
for (let i: number = 3; i < nums.length; i++) {
let t = Math.max(t0, t1) + nums[i];
t0 = t1;
t1 = t2;
t2 = t;
}
return Math.max(t1, t2);
};点评
从前开始往后计算包含当前索引的最大和，简化为前面隔两个和隔一个加上当前值取最大值。
理由是如果间隔了三个都没有取值，那加上中间这个一定更大，所以最多只会间隔两个数。
因为没有负值，所以可以这样做，否则应该要换算法。
计算到最后一个，取后两个里的最大值。
不过初始化比较啰嗦，开始的边界条件写了四个判断。
根据官方解法，我还是想复杂了一步，没必要关心是隔一个还是两个，直接取隔一个加上当前值和前一个对比就行了。
时间效率虽然是100%，空间上还是多用了一个变量。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog