如何使用递归正确退出对房子强盗实现？

Question

我在做抢屋者挑战。

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{

Answer 1

问题是我通过两种方法迭代。一个“for循环”和单元+1。我在递归的核心部分搞砸了。不使用'for循环'，只使用单元+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