1、前言
题目描述
2、思路
定义 f(i) = 从前 i 个房屋中能抢劫的最大金额，Ai = 第 i 个房屋的钱数。
首先我们看 n = 1 的情况，显然 f(1) = A1。
再看 n = 2 的情况，f(2) = max(A1, A2)。
再看 n = 3 的情况，可以有两个选项可以选择：
抢第三个房子，那么意味着不能抢第二个房子，并且还可以抢第一个房子：f(i - 2) + A3。
不抢第三个房子，那么意味着保持最大数额即可：f(i - 1)。
因此，动态规划公式为：f(i) = max{f(i - 1), f(i - 2) + Ai}，初始情况，f(0) = 0，f(1) = A1。
3、代码
/*
* 动态规范，转移方程：dp(n) = max{ dp(n - 1), dn(n - 2) + num}
*/
class Solution {
public int rob(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
int[] dp = new int[nums.length + 1];
dp[0] = 0;
dp[1] = nums[0];
for(int i = 2; i <= nums.length; i++){
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
}
return dp[nums.length];
}
}
