力扣hot100：打家劫舍

题目描述：

动态规划思路描述：

• 状态定义：
  定义dp[i]表示偷窃前i个房子的最大金额。
  那么，对于第i个房子，我们有两种选择：

  • 不偷：如果我们不偷当前的房子，那么最大金额就是前一个房子的最大金额，即dp[i-1]。

  • 偷：如果我们偷了当前的房子，那么最大金额就是前一个房子不能偷的情况下，加上当前房子的金额，即dp[i-2] + nums[i]。

  因此，状态转移方程为：
  dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])

代码解析：

class Solution { public int rob(int[] nums) { int pre=0; int cur=0; int temp; for(int num:nums){ temp=cur; cur=Math.max(cur,pre+num); pre=temp; } return cur; } }

由于dp[n] 只与 dp[n−1] 和 dp[n−2] 有关系，因此我们可以设两个变量cur和pre交替记录，cur表示dp[n−1] ，pre表示dp[n−2]，开始由于一栋房子也没偷，cur和pre均为0，num是当前房子的价格，在循环中遍历房子。