Question

题目内容

解题思路

动态规划。

五部曲：

1. 确定 dp 数组及下标含义：dp[i]：下标 i(包括 i) 以内的房屋，最多可以偷窃的金额为 dp[i]。
2. 确定递推公式：dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])。
   决定 dp[i] 的因素是第 i 个房间偷还是不偷：
   • 偷：dp[i] = dp[i - 2] + nums[i]。
   • 不偷：dp[i] = dp[i -1]，考虑 i - 1 房。
3. dp 数组初始化：dp[0] = nums[0]，dp[1] = Math.max(nums[0], nums[1])。
4. 确定遍历顺序：从前到后遍历，i 初始化为 2。
5. 举例推导验证。

代码实现

const rob = (nums: number[]): number => {
  const len: number = nums.length;
  const dp = [nums[0], Math.max(nums[0], nums[1])];
  for (let i = 2; i < len; ++i) {
    dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
  }
  return dp[len - 1];
};