讨论/技术交流/交流探讨 | 打家劫舍问题/
交流探讨 | 打家劫舍问题

如果说在打家劫舍问题上加入,只能允许偷三家的条件。并且要知道是偷的哪三家?该怎么解决呢?

共 3 个回复

假设设置至多K的条件,那么可以用动态规划记录之前的数量,复杂度是O(NK)O(NK)的.
但实际上这个问题可以对K=1,2,,N2K=1,2,\cdots,\lceil\dfrac{N}2\rceil全部求出做到O(NlogN)O(N\log N).
做法可以参考种树.

5

可以参考限制交易次数的股票问题,用动态规划解决。要知道偷的是哪三家,像前几天的整除子集一样记录一下从哪一个状态转移而来就行。

应该用回溯法吧,遍历所有可能,然后超过最大值的三个数,更新到list里