Skip to content

Latest commit

 

History

History
 
 

213.House-Robber-II

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

213.House-Robber-II

解法1:双状态动态规划

考虑环的影响,首位和末位不能同时为yes。这说明至少有一个的选择是no。

(1) 如果首位我们选择no,那么从nums[1]到nums[n-1]的选择就没有环形的首尾制约,完全就是一个198.House Robber I的问题。

(2) 如果末位我们选择no,那么从nums[0]到nums[n-2]的选择就没有环形的首尾制约,同样也是一个198.House Robber I的问题。

我们将两种情况下的最优解再取最大值,就是答案。

注意,(1)和(2)并不是互斥的。他们是有交叠的。但是它们的并集一定是全集。

解法2:记忆化搜索(递归)

我们考虑是否打劫第零家(nums[0]):是的话,那么下一步我们可以在[2,n-2]中任意选择打劫。如果不打劫第零家,那么下一步我们可以在[1,n-1]中任意选择打劫。也就是说,最顶层的答案就是max( nums[0]+dfs(2,n-2), dfs(1,n-1) )其中DFS的两个参数就是可供打劫的区间。这里特别注意的是n-2,这是因为题目中loop的要求(不能打劫任意相邻两家),打劫了第0家的话我们就不可能打劫第n-1家。

对于任意区间[i,j]作为打劫对象,我们可以同样处理,考虑是否打劫最前面的(也就是第i家)。根据不同的决策,我们分别有:nums[i]+dfs(i+1,j)dfs(i+1,j).两者分别递归处理得到结果后,取较大作为返回值。

当然,我们也可以用区间型的二维dp来实现上面的算法。

Follow-up

此题有一个更难一点的follow up,参见1388.Pizza-With-3n-Slices.

Leetcode Link