题解 | #切割成本#
切割成本
http://www.nowcoder.com/practice/5c5fa5bf2a9942fcb1a3844d715087b9
题意
长最大为1000000的线段上,给n个点。
其中每选择一个点,线断根据这个点分成两段,代价为这个线段的长度
找一个点的序列,使得代价总和最小,求这个最小代价。
其中n<300
方法
递归分治(TLE)
以题目为例[2,5,10,18]
表示成图就是
--|---|-----|--------|--
任选一处分成两段后,子线段的分割方案对父线段的分割方案无影响。所以这个问题可以分治。
枚举所有点,每次选择一个点,f(线段)=线段长度+min(f(选点左侧的线段)+f(选点右侧的线段))
因此实现如下
代码
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
#
# @param monsterLength int整型 线段长度
# @param monsterPoint int整型一维数组 切割点位置
# @return int整型
#
class Solution:
def attackMonster(self , monsterLength , monsterPoint ):
monsterPoint.sort()
if len(monsterPoint) == 0:
return 0
ans = 0x3f3f3f3f
for i in range(len(monsterPoint)):
ans = min(ans,
monsterLength
+ self.attackMonster(monsterPoint[i], monsterPoint[:i])
+self.attackMonster(monsterLength-monsterPoint[i],[v-monsterPoint[i] for v in monsterPoint[i+1:]]))
return ans
复杂度分析
时间复杂度: 因为我们采取递归的方式,从上向下以此尝试了所有方案,所以时间复杂度为O(n!)
空间复杂度: 空间复杂度与递归深度相关,所以复杂度为O(n)
DFS+记忆化
由题目的样例1,有4种分法
2 | 3 | 5 | 8 | 2 |
---|---|---|---|---|
左 | 右 | 右 | 右 | 右 |
左 | 左 | 右 | 右 | 右 |
左 | 左 | 左 | 右 | 右 |
左 | 左 | 左 | 左 | 右 |
对每种分法的子线段[2],[2,3],[2,3,5],[2,3,5,8],[3,5,8,2],[5,8,2],[8,2],[2]
, 仍然是一个连续数组的分割,因此实际上所有的分割,都属于[节点左,节点右]
因此状态数为O(节点2)
因此使用记忆化来优化重复计算。
代码
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
#
# @param monsterLength int整型 线段长度
# @param monsterPoint int整型一维数组 切割点位置
# @return int整型
#
class Solution:
mem = []
# sti 节点 + 0~sz-1 的节点是可切割的
# 线段 [sti-1...sti+sz]
def dfs(self, p, sti, sz):
if sz == 0:
return 0
if self.mem[sti][sz] != 0x3f3f3f3f: # 记忆化
return self.mem[sti][sz]
ans = 0x3f3f3f3f
for i in range(sz):
ans = min(ans,
p[sti+sz] - p[sti-1]
+ self.dfs(p, sti, i) # 左
+ self.dfs(p, sti+i+1, sz - i -1) # 右
)
self.mem[sti][sz] = ans
return ans
def attackMonster(self , monsterLength , monsterPoint ):
monsterPoint.sort()
self.mem = [[0x3f3f3f3f for i in range(len(monsterPoint)+2)] for j in range(len(monsterPoint)+2)]
# 增加首位节点 方便计算
return self.dfs([0]+monsterPoint+[monsterLength],1,len(monsterPoint))
复杂度分析
时间复杂度: 因为我们采取递归的方式,但是有记忆化辅助,每个状态最多计算自己一次,每个状态依赖常数个其它状态,因此时间复杂度为O(n2)
空间复杂度: 空间复杂度与递归深度和状态数量相关,状态数量其实就是所选的子数组的种类数,所以复杂度为O(n2)