swift - House Robber实现如何使用递归正确退出？

Question

我正在做 House Robber challenge .

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

我的代码:

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 

---

我的迭代策略是:

• 如果前一个已经被抢劫，那么我只能不在我的下一个迭代中抢劫。
• 如果前一个没有被抢劫，那么我可以在我的下一次迭代中抢劫或不抢劫。显然，为了找到所有有效的抢劫，我都做了!

我的退出策略是在下面一行完成的:

if i == neighborUnits.count - 1{

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

然后我将该值与 mostMoneyRobbed 进行比较，如果它更大，我将我的值设置为该值。在循环结束时，我只返回 mostMoneyRobbed

但在到达 block 的最后一个元素并返回后，我的代码继续进行!!!!我不明白为什么。应该是很琐碎的事情

请注意我不需要替代解决方案。我想修复我自己的实现。

Answer 1

问题是我正在通过两种方式进行迭代。 “for 循环”和 unit + 1。我有点搞砸了递归的核心。不使用“for 循环”，仅使用 unit + 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 个测试用例上遇到了 Time Limit Exceeded 错误! :D