LeetCode.198.打家劫舍（中等）

题目

LeetCode.198.打家劫舍（中等）

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

题解

思路

最优化问题，考虑是否符合动态规划的条件：最优子结构、重叠子问题、无后效性。
从最终状态做倒推，穷举列出到达最终状态所需要的最小步骤，看是否能从上一个状态加上有限步骤得到最终状态，检查上一个状态的最优解是否也能通过不停的倒推拆解得到，拆分步骤的过程可得出状态转移方程。拆分到最开始，做边界条件处理。

划分子问题

设nums[i]为第i间房屋金额。
设dp[i]为达到第i个房屋时能偷到的最高金额。

1. 偷第i间房，就不能偷第i - 1房，dp[i] = dp[i - 2] + nums[i]
2. 不偷第i间房，dp[i] = dp[i - 1]

边界条件

1. 只有1间房，直接偷
2. 只有2间房，由于不能偷相邻的房间，就偷钱多的。

空间优化

dp[i]只从前两项递推得来，所以不需要数组记录所有状态，只需要两个变量记录递推的状态。

代码

class Solution {
    fun rob(nums: IntArray): Int {
        val n = nums.size
        if (n == 0) return 0
        if (n == 1) return nums[0]
        var pre2 = nums[0]
        var pre1 = maxOf(nums[0], nums[1])
        var cur = pre1 
        for (i in 2 until n) {
            cur = maxOf(pre1, pre2 + nums[i])
            pre2 = pre1
            pre1 = cur
        }
        return cur
    }
}