代码之家 › 专栏 › 技术社区 › mfaani

如何正确使用递归退出实现抢劫?

dynamic-programming iteration recursion algorithm swift

mfaani · 技术社区 · 6 年前

你是一个计划沿着街道抢劫房屋的专业抢劫犯。每套房子都藏了一定数量的钱,这是唯一的限制阻止你抢劫他们的是附近的房子安全系统已连接,将自动联系警方如果两个相邻的房子在同一个晚上被闯入。

给出一个表示货币量的非负整数列表在每栋房子里,确定你能抢劫的最大金额今晚没有报警。

我的代码 :

class Solution {
    func rob(_ nums: [Int]) -> Int {
        var mostMoneyRobbed = 0

        func rob(neighborUnits: [Int], startfromUnit unit: Int, didRobAdjacentUnit: Bool, totalMoneyRobbed total: Int){

            if total > mostMoneyRobbed{
                mostMoneyRobbed = total
            }
            for i in unit...neighborUnits.count - 1{
                if i == neighborUnits.count - 1{
                    if !didRobAdjacentUnit{
                        if total + nums[i] > mostMoneyRobbed{                                
                            mostMoneyRobbed = total + nums[i]                                
                        }
                    }
                    return
                }

                if didRobAdjacentUnit{
                    rob(neighborUnits: nums, startfromUnit: unit + 1, didRobAdjacentUnit: false, totalMoneyRobbed: total)
                }else{
                    rob(neighborUnits: nums, startfromUnit: unit + 1, didRobAdjacentUnit: true, totalMoneyRobbed: total + nums[i])
                    rob(neighborUnits: nums, startfromUnit: unit + 1, didRobAdjacentUnit: false, totalMoneyRobbed: total)
                }
            }            
        }
        guard nums.count > 0 else {
            return 0
        }

        rob(neighborUnits: nums, startfromUnit: 0, didRobAdjacentUnit: true, totalMoneyRobbed: 0)
        rob(neighborUnits: nums, startfromUnit: 0, didRobAdjacentUnit: false, totalMoneyRobbed: 0)

        return mostMoneyRobbed
    }
}

用途:

let s = Solution()
print(s.rob([1,2,3])) // returns 5 instead of 4

我的迭代战略是:

如果以前的被抢了,我只能不 Rob在我的下一个迭代中。
如果以前的没有被抢,我可以 任何一个 在下一次迭代中是否是Rob。显然,要找到所有有效的抢劫,我都要做!

我的出口策略在下面的行中完成:

if i == neighborUnits.count - 1{

基本上,如果我到达单元的末尾,迭代就会停止。

然后我将值与 mostMoneyRobbed 如果它更大,我就把我的价值定为这个。在循环结束时,我只是返回 大多数都是假的

然而,在到达块的最后一个元素并返回代码后,继续进行!!!!!我不明白为什么。它应该是一些非常微不足道的东西

请注意 我不想要其他的解决方案。我想修复自己的实现。

1 回复 | 直到 6 年前

mfaani 6 年前

问题是我正在迭代两种方法。a“for loop”和 Unit+1 。我有点搞砸了递归的核心。不使用“for loop”,只使用 Unit+1 was all that was needed.

类解决方案{ func rob(unums:[int])->int{ var mostmoneyrobbed=0 func rob(neighborunits:[int],startfromunit:int,didrobajacentunit:bool,totalmoneyrobbed total:int){ 如果总数超过大多数,则取消{ mostMoneyRobbed=总计 } 如果单位=neighborunits.count-1{ 如果!双机器人相邻单元{ 如果总计+nums[单位]>mostmoneyrobbed{ mostmoneyrobbed=总数+数字[单位] } } 返回 } 如果是双相邻单元{ rob(neighborunits:nums,startfromunit:unit+1,didrobajacentunit:false,totalmoneyrobbed:total) }否则{ rob(邻居单位:nums,开始单位:Unit+1,didrobajacentUnit:true,totalmoneyrobbed:total+nums[单位]) rob(neighborunits:nums,startfromunit:unit+1,didrobajacentunit:false,totalmoneyrobbed:total) } } guard nums.count>1其他{ 如果nums.count==0{ 返回0 }否则{ 返回数字[0] } } rob(邻居单位:nums,开始单位:0,didrobajacentUnit:true,totalmoneyrobbed:0) rob(neighborunits:nums,startfromunit:0,didrobajacentunit:false,totalmoneyrobbed:0) 返回mostmoneyrobbed } }


到目前为止,这已达到预期效果。在leetcode上,我得到了一个超过时间限制的第49个测试用例的错误!d



e“for loop”并仅使用单位+1只需要这些。

class Solution {
    func rob(_ nums: [Int]) -> Int {
        var mostMoneyRobbed = 0

        func rob(neighborUnits: [Int], startfromUnit unit: Int, didRobAdjacentUnit: Bool, totalMoneyRobbed total: Int){

            if total > mostMoneyRobbed{
                mostMoneyRobbed = total
            }
            if unit == neighborUnits.count - 1{
                if !didRobAdjacentUnit{
                    if total + nums[unit] > mostMoneyRobbed{
                        mostMoneyRobbed = total + nums[unit]
                    }
                }
                return
            }

            if didRobAdjacentUnit{
                rob(neighborUnits: nums, startfromUnit: unit + 1, didRobAdjacentUnit: false, totalMoneyRobbed: total)
            }else{
                rob(neighborUnits: nums, startfromUnit: unit + 1, didRobAdjacentUnit: true, totalMoneyRobbed: total + nums[unit])
                rob(neighborUnits: nums, startfromUnit: unit + 1, didRobAdjacentUnit: false, totalMoneyRobbed: total)
            }
        }
        guard nums.count > 1 else{
            if nums.count == 0{
                return 0
            }else{
                return nums[0]
            }
        }

        rob(neighborUnits: nums, startfromUnit: 0, didRobAdjacentUnit: true, totalMoneyRobbed: 0)
        rob(neighborUnits: nums, startfromUnit: 0, didRobAdjacentUnit: false, totalMoneyRobbed: 0)

        return mostMoneyRobbed
    }
}


到目前为止,这已达到预期效果。在Leetcode上我有一个超过时间限制第49个测试用例出错!D