原题地址
https://leetcode.com/problems/house-robber/
题目描述
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.
给出一系列非负的整数代表每个房子内的金钱数量，计算你今晚不触发报警条件的情况下可以抢到的最多的钱。
Tags
Dynamic Programming
解题思路
对于求解这个问题，关键问题是对于某间房子，我们抢还是不抢。假设我们用rob[i]表示抢劫第i间房子的情况下在之后的所有房子里可以得到的最大金额，用notRob[i]表示不抢劫第i间房子的情况下在之后的所有房子里可以得到的最大金额。在
求解rob[i]时，抢劫第i间房子，很明显不能继续抢劫它的下一间房子
，因此rob[i]需要根据notRob[i+1]来计算，
对于notRob[i]，我们不抢第i间房子时，第i+1间房子既可以抢也可以不抢
，我们根据rob[i+1]和notRob[i+1]之间的较大者来计算notRob[i]。
rob[i]
: 在抢劫第i间房子的情况下，可以从其之后的所有房子里（
nums[i]~nums[n]
）获得的金钱。
notRob[i]
: 在不抢劫第i间房子的情况下，可以从其之后的所有房子里（
nums[i]~nums[n]
）获得的金钱。
有如下方程来计算：
r
o
b
[