一、题目描述
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 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 。
二、解题思路
动态规划的思想：进入一个屋子，要么盗窃，要么不盗窃；由于不可以在相邻的房屋闯入，所以在当前位置 n 房屋可盗窃的最大值，要么就是 n-1 房屋可盗窃的最大值，要么就是 n-2 房屋可盗窃的最大值加上当前房屋的值，二者之间取最大值
举例：
存在数组[3, 4, 2], 则1 号房间可盗窃最大值为 3 即为 dp[1]=3，2 号房间可盗窃最大值为 4 即为 dp[2]=4，3 号房间自身的值为 2 即为 num=2，那么 dp[3] = MAX( dp[2], dp[1] + num ) = MAX(4, 3+2) = 5，即3 号房间可盗窃最大值为5
动态规划方程:
dp[n] = MAX( dp[n-1], dp[n-2] + num )
三、代码实现
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size();
if (len == 0) return 0;
int dp[len+1];
dp[0] = 0;
dp[1] = nums[0];
for (int i = 2; i <= len; i++) {
dp[i] = max(dp[i-1], nums[i-1] + dp[i-2]);
}
return dp[len];
}
};
四、总结
动态规划（英语：Dynamic programming，简称DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。
dp问题应当好好掌握，相似题目有：爬楼梯、最长递增子序列等。
