打家劫舍

题目：

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

示例：

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

解题方法：

这道题和之前的爬阶梯相似，从大到小考虑思路会更清晰：

当小偷偷到第n间房子，那么：dp[n]={dp[n-2]+nums[n]，dp[n-1]}

递推公式的意思就是，当偷到第n间房子，最大金额有两种可能：一种是不偷，那么dp[n]就是dp[n-1]；还有一种可能就是偷，那就得从dp[n-2]累加，dp[n]=dp[n-2]+nums[n]；最后就是推到0，1，2间房子的时候，直接进行判断就可以了。

代码和结果：

class Solution {
public:
    int rob(vector<int>& nums) {
        int len=nums.size();
        if(len==0)
            return 0;
        else if(len==1)
            return nums[0];
        else if(len==2)
            return nums[0]>nums[1]?nums[0]:nums[1];
        else
        {
            int maxv;
            int dp0=nums[0];                            //dp[i-2]
            int dp1=nums[0]>nums[1]?nums[0]:nums[1];    //dp[i-1]
            for(int i=2;i<nums.size();i++)
            {
                int cur=nums[i]+dp0;
                maxv=cur>dp1?cur:dp1;
                dp0=dp1;
                dp1=maxv;
            }
            return maxv;
        }
    }
};

运行结果:

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