Leetcode198

题目标签

动态规划

解题思路

首先考虑最简单的情况。如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。

如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？对于第 k(k>2)间房屋，有两个选项：

偷窃第k间房屋，那么就不能偷窃第k-1间房屋，偷窃总金额为前k-2间房屋的最高总金额与第k间房屋的金额之和。

不偷窃第k间房屋，偷窃总金额为前k-1间房屋的最高总金额。

在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 kk 间房屋能偷窃到的最高总金额

用dp[i]表示前i间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：

dp[i]=max(dp[i−2]+nums[i],dp[i−1])

边界条件为：

dp[0] = nums[0] -> 只有一间房屋，则偷窃该房屋

dp[1] = max(nums[0],nums[1]) -> 只有两间房屋，选择其中金额较高的房屋进行偷窃

最终的答案即为 dp[n−1]，其中n是数组的长度。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

func rob(nums []int) (ans int) {
    if len(nums) == 1 {
        return nums[0]
    }
    dp := make([]int,len(nums))
    dp[0] = nums[0]
    dp[1] = max(nums[0],nums[1])
    for i := 2; i < len(nums); i++ {
        dp[i] = max(dp[i - 2] + nums[i],dp[i - 1])
    }
    return dp[len(dp) - 1]
}
func max(i,j int) int {
    if i > j {
        return i
    }
    return j
}

• ← Previous Post
• Next Post →