LeetCode 198 入室抢劫者

1 题目描述

假设您是一个老练的盗贼,计划沿着街道进行打家劫舍。该街道每家都存着一定数额的钱,而阻止您进行盗窃的唯一屏障是相邻两家的防盗系统是连接的,若相邻两家在同一晚都发生了盗窃案,该系统会自动通知到警察。

现在给定一个非负整数数组,代表该街道沿线每家的金钱数额,请计算在不触发系统通知警察的情况下,您今晚能盗窃的最大金钱数额。

例子1:

输入:[1,2,3,1]

输出:4

释义:先盗第1家,盗窃金钱1,然后再盗第3家,盗窃金钱3,总数为1 + 3 = 4。

例子2:

输入:[2,7,9,3,1]

输出:12

释义:分别去盗第1、3、5家,盗窃总金额为2 + 9 + 1 = 12。

题目出处:LeetCode

2 解决思路

逆向思考,先站在最后一家门口算一算,盗与不盗的最大利益。

这家盗的最大金额为:截至到上上家盗取的最大金额 + 这家的金额

这家不盗的最大金额为:截至到上一家盗取的最大金额

以此类推,直至递归到第1家,或第0家(空)。

因递归时用到的很多子计算是重复的,我们使用table存取截至到第i家盗取的最大金额,首次计算后写入,再次需要时直接返回,实现加速。

3 Golang实现代码

https://github.com/olzhy/

func recusiveRob(nums []int, len int, table map[int]int) int {
    if 0 == len {
        return 0
    }
    if 1 == len {
        return nums[0]
    }
    if v, ok := table[len]; ok {
        return v
    }
    max := recusiveRob(nums, len-2, table) + nums[len-1]
    pre := recusiveRob(nums, len-1, table)
    if pre > max {
        max = pre
    }
    table[len] = max
    return max
}

func rob(nums []int) int {
    table := make(map[int]int)
    return recusiveRob(nums, len(nums), table)
}
若觉得文章对您有所帮助,可以请我喝杯咖啡,Thanks!
微信 支付宝