这里分享一道关于dp的题目，题目如下：
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
这题是leetcode上198题，思路就是对于第i个房子，你有两个选择：
- 抢劫这个房子，这样就只能再抢
i-2的房子 - 不抢这个房子，这样就抢
i-1的房子
写成递归形式：rob(i) = Math.max( rob(i - 2) + currentHouseValue, rob(i - 1) )
根据这个递归式子写出递归的解法很简单，但是其实递归的过程是有重复的，因此可以改进为递归加“记忆”的形式来减小空间复杂度。再进一步优化，可以改成dp的形式。但是这里并不需要n个空间，其实只需要2个变量就够了。最终的代码可以看下面：
public int rob(int[] nums) {
int prev1=0;
int prev2=0;
for(int num:nums){
int tmp = prev1;
prev1 = Math.max(prev2+num,prev1);
prev2 = tmp;
}
return prev1;
}
具体的优化过程可以看这里，这个老哥写的很详细，对于每一步是怎么得出来的都写的很清楚，这里就不写了。
