LeetCode题解：198. 打家劫舍，动态规划（缓存偷盗状态），JavaScript，详细注释

[chencl1986]

原题链接：https://leetcode-cn.com/problems/house-robber/

解题思路：

1. 对于第i户人家，有偷和不偷两种可能。
   • 如果偷，i - 1户人家只能不偷。
   • 如果不偷，i - 1户人家偷不偷都可以，此时取i - 1户两个状态的最大值即可。
2. 状态转移方程：dp[i] = [dp[i - 1][1] + nums[i], Math.max(dp[i - 1][0], dp[i - 1][1])];。
3. 偷到最后一户时，只需要取其最大值，就是最高金额。

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  // 对于第一户人家，存在偷和不偷两种情况
  // 需要注意nums为[]的情况，此时偷的情况也为0
  let dp = [[nums[0] || 0, 0]];

  // 判断每一户人家的偷和不偷状态，不断累加偷到的金额
  for (let i = 1; i < nums.length; i++) {
    dp[i] = [
      // 如果偷当前人家，那么上一户人家就不能偷，只能取不偷的值
      dp[i - 1][1] + nums[i],
      // 如果不偷当前人家，上一户人家偷不偷都可以，只需要取一个最大值
      Math.max(dp[i - 1][0], dp[i - 1][1]),
    ];
  }

  // 数组最后一位，分别存储了偷和不偷最后一户的总金额，取最大值即可
  return Math.max(...dp[dp.length - 1]);
};