动态规划(Dynamic Programming)是一种分阶段求解决策问题的数学思想,它通过把原问题分解为简单的子问题来解决复杂问题。

打家劫舍

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

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1： 输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。   偷窃到的最高金额 = 1 + 3 = 4 。

示例 2： 输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。   偷窃到的最高金额 = 2 + 9 + 1 = 12 。

思路

根据题意我们知道不能不同偷窃相邻的两个房间，即：

1. 如果偷窃第i间房屋，那么就不能偷窃第i-1间房屋，一夜之内能够偷窃到的最高金额为前 i-2 间房屋的最高总金额与第i间房屋的金额之和。
2. 如果不偷窃第i间房屋，那么能够偷窃到的最高金额为前 i-1 间房屋的最高总金额。

所以如果房间总数为i，那么一晚上能偷到的最大金额为dp[i]=max(dp[i−2]+house[i],dp[i−1])。

考虑3种特殊情况：

1. 没有房间，偷无可偷，最大金额为0。
2. 只有一间房，那么直接偷窃该房屋。即dp[0]=house[0]。
3. 总共有2间房，因为不能偷窃相邻的，所以只能选金额最大的偷窃，即dp[1]=math(house[0],house[1])。

代码如下：

fun rob(nums: IntArray): Int {
    if (nums.isEmpty()) {
        return 0
    }
    val length = nums.size
    if (length == 1) {
        return nums[0]
    }
    val dp = IntArray(length)
    dp[0] = nums[0]
    dp[1] = Math.max(nums[0], nums[1])
    for (i in 2 until length) {
        dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])
    }
    return dp[length - 1]
}

复杂度分析

• 时间复杂度：O(n)，只需跑一遍房屋即可。
• 空间复杂度：O(n)。使用数组存储了房屋的最高总金额。