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 。来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/house-robber 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
这是一道非常典型且简单的动态规划问题，但是在这里我希望通过这个例子， 让大家对动态规划问题有一点认识。
为什么别人的动态规划可以那么写，为什么没有用 dp 数组就搞定了。比如别人的爬楼梯问题怎么就用 fibnacci 搞定了？为什么？在这里我们就来看下。
思路还是和其他简单的动态规划问题一样，我们本质上在解决 对于第[i]个房子，我们抢还是不抢。的问题。
判断的标准就是总价值哪个更大， 那么对于抢的话 就是当前的房子可以抢的价值+dp[i-2]
i - 1 不能抢，否则会触发警铃
如果不抢的话，就是 dp[i-1].
这里的 dp 其实就是
子问题.
状态转移方程也不难写 dp[i]=Math.max(dp[i-2]+nums[i-2],dp[i-1]);.
上述过程用图来表示的话，是这样的：
我们仔细观察的话，其实我们只需要保证前一个 dp[i - 1] 和 dp[i - 2] 两个变量就好了， 比如我们计算到 i = 6 的时候，即需要计算 dp[6]的时候， 我们需要 dp[5], dp[4]，但是我们 不需要 dp[3], dp[2] ...
因此代码可以简化为：
let a = 0;
let b = 0;
for (let i = 0; i < nums.length; i++) {
const temp = b;
b = Math.max(a + nums[i], b);
a = temp;
}
return b;如上的代码，我们可以将复杂度进行优化，从 O(n)降低到 O(1), 类似的优化在 DP 问题中不在少数。
动态规划问题是递归问题查表，避免重复计算，从而节省时间。如果我们对问题加以分析和抽象，有可能对空间上进一步优化
关键点解析
代码
/*
* @lc app=leetcode id=198 lang=javascript
*
* [198] House Robber
*
* https://leetcode.com/problems/house-robber/description/
*
* algorithms
* Easy (40.80%)
* Total Accepted: 312.1K
* Total Submissions: 762.4K
* Testcase Example: '[1,2,3,1]'
*
* You are a professional robber planning to rob houses along a street. Each
* house has a certain amount of money stashed, the only constraint stopping
* you from robbing each of them is that adjacent houses have security system
* connected and it will automatically contact the police if two adjacent
* houses were broken into on the same night.
*
* Given a list of non-negative integers representing the amount of money of
* each house, determine the maximum amount of money you can rob tonight
* without alerting the police.
*
* Example 1:
*
*
* Input: [1,2,3,1]
* Output: 4
* Explanation: Rob house 1 (money = 1) and then rob house 3 (money =
* 3).
* Total amount you can rob = 1 + 3 = 4.
*
* Example 2:
*
*
* Input: [2,7,9,3,1]
* Output: 12
* Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house
* 5 (money = 1).
* Total amount you can rob = 2 + 9 + 1 = 12.
*
*
*/
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function(nums) {
// Tag: DP
const dp = [];
dp[0] = 0;
dp[1] = 0;
for (let i = 2; i < nums.length + 2; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i - 2], dp[i - 1]);
}
return dp[nums.length + 1];
};