leetcode: 198. 打家劫舍

链接：https://leetcode-cn.com/problems/house-robber/

设dp[i - 1]表示前 i - 1 间房子能偷窃到的最高金额。

那么对于前 i 间房子，能偷窃到的最高金额：

（1）第 i 间房子不偷。此时dp[i] = dp[i - 1]

（2）第 i 间房子偷。此时dp[i] = dp[i - 2] + nums[i]

状态转移方程 dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

class Solution {
    // dp[i]：前i个房间能偷窃到的最高金额
    // dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
    public int rob(int[] nums) {
        // 只和dp[i - 1], dp[i - 2]，所以只需定义两个变量表示即可，空间复杂度降为O(1)
        // cur 即 dp[i - 1]，prev 即 dp[i - 2]
        int cur = 0, prev = 0, temp = 0;
        for (int num : nums) {
            temp = cur;
            cur = Math.max(prev + num, cur);
            prev = temp;
        }

        return cur;
    }
}

image-20210505182947080.png