打家劫舍问题

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。（即不能偷相邻的房屋，但是不一定只能隔着一个偷）
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

例：

输入：[1,2,3,1]

输出：4

偷1号+偷3号

输入：[10,4,2,5]

输出：15

偷1号+偷4号
 

题目分析：采用动态规划

动态规划解题步骤

• 定义子问题
• 写出递推表达式
• 确定计算顺序

子问题与原问题相似，规模减小。要我们求n个房子中最大金额，可以通过其他子问题的解求出原问题的解。就是将一个问题转换为更小的问题来解决，每个问题的解其实由最优子问题组成。

假设总共n个房子，房子中的金额存储在nums数组中，数组下标由0开始。那么第n个房子的金额为nums[n-1]，求偷到第n个房子的最大金额有两种。

(1)偷第n个房子，那么第n-1个房子我们就不能偷了，累计金额为在k-2间累计偷到的最大值+当前nums[n-1]

(2)不偷第n个房子，累计金额为在k-1间累计偷到的最大值

注意：

在这其中dp[n-1]不一定被偷，但是它的最大金额dp[n-1]是继承前面可能是dp[n-2]的，但是此时dp[n-1]=dp[n-2]没有影响，也就是上面的dp[n-1]

题目要求得到偷取的最大金额所以在这两种可能中取最大max（dp[k-1],nums[k-1]+dp[k-2])

还要注意n=0,n=1时

当n=0时，dp[0]=0;没有房子

当n=1时，dp[1]=nums[0];只有一间

在其他题目边界条件n=0很重要，防止没有终止。但这道题我们是从前往后推，dp[n]依赖于dp[n-1]、dp[n-2]从左向右的也就是依赖的子问题已经被计算出来了，边界只在最后一间房子。

class Solution {
public:
    int rob(vector& nums) {
    if (nums.size() == 0) {
        return 0;
    }
    //其实不一定隔着一个偷但是当你到下一间时就是这一间的前一间没被偷它也可以dp[n-1]=dp[n-2]，假设被偷的是第n间

    int N = nums.size();
    vector dp(N+1, 0);
    dp[0] = 0;
    dp[1] = nums[0];
    for (int k = 2; k <= N; k++) {
        dp[k] = max(dp[k-1], nums[k-1] + dp[k-2]);
    }
    return dp[N];
}
    };