198.打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

输入：[2,7,9,3,1] 输出：12

1. 动规。dp[i][0]表示第i间房子不偷窃所得最高金额，dp[i][1]表示偷窃第i间房子的最高金额。状态转移方程：dp[i][0]=Math.max(dp[i-1][1],dp[i-1][0])，dp[i][1]=Math.max(dp[i-2][1]+nums[i],dp[i-1][0]+nums[i])空间大小O(2n)。

• 可以只开辟O(n)空间，dp[i]表示考虑第i间房子所能获得的最高金额。则有 dp[i]=max(偷窃第i间房子，不偷窃第i间房子)=Math.max(dp[i-2]+nums[i]，dp[i-1])，注意我们完全不需要关注dp[i]到底是偷了还是没偷，如果i-1间房子没偷，dp[i-2]等于dp[i-1]，结果是一样的。
• 更进一步优化，只需要两个变量维护前两个房间最高金额+一个变量维护当前房间最高金额。空间O(1)