動機

控制input的dp

Problem

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

 

Example 1:

Input: nums = [2,3,2]Output: 3Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Example 2:

Input: nums = [1,2,3,1]Output: 4Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).Total amount you can rob = 1 + 3 = 4.

Example 3:

Input: nums = [0]Output: 0

 

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000

Ver1: TLE

假DP，真bfs

from collections import deque
class Solution:
    def rob(self, ns: List[int]) -> int:
        def toMark(i):
            a = (i + 1) % len(ns)
            b = i - 1 if i - 1 >= 0 else len(ns) - i - 1
            ret = [a,b,i]
            ret.sort()
            return set(ret)
        dp = {} #set:: possible next location
        q = deque([tuple(range(0,len(ns)))])
        dp[tuple(range(0,len(ns)))] = 0
        ans = 0
        while q:
            pos = q.popleft()
            
            set_pos = set(pos)
            for i in pos:
                next_pos = tuple(set_pos - toMark(i))
                #print(next_pos,i,set_pos,toMark(i), dp[pos])
                tmp = ns[i] + dp[pos]
                dp[next_pos] = tmp
                ans = max(ans,tmp)
                if next_pos:
                    q.append(next_pos)
        return ans

Ver2: AC

上一個做法是列舉所有可能的next_pos，這會有一些問題

  1. 會到之前我們走過的點
  2. 在一個點上，我們無法確定之前是從哪個點過來的

如果一開始就造出不會有circular的Input，這樣就可以用House Robber的解法了，故 劃出範圍當成House Robber來做就好了， 看來這種不能用index來區分範圍的，不用考量到dp中

@dp = nil
@nums = nil
def f(i)
    if @dp[i] != -1
        return @dp[i]
    else
        ans = 0
        (0..i-2).each { |j| ans = f(j) if f(j) > ans }
        @dp[i] = @nums[i] + ans
    end
end
def rob1(nums)
    return 0 if nums.nil? || nums.size == 0
    @nums = nums
    @dp = Array.new(nums.size, -1)
    (0...nums.size).to_a.map { |n| f(n) }.max
end
def getRange(i,nums)
    a = i-1 >= 0 ? nums.size  : nums.size + (i-1)
    b = (i+1) >= nums.size ? nums.size : (i+1)
    b+=1
    return nums[b...a]
end
def rob(nums)
    ans = 0
    nums.size.times do |i|
        ans = [ans,rob1(getRange(i,nums))+nums[i]].max
    end
    ans
end