题意

长最大为$10000001000000$1000000的线段上，给n个点。

其中每选择一个点，线断根据这个点分成两段，代价为这个线段的长度

找一个点的序列，使得代价总和最小，求这个最小代价。

其中n<300

方法

递归分治（TLE）

以题目为例[2,5,10,18]

表示成图就是

--|---|-----|--------|--

任选一处分成两段后，子线段的分割方案对父线段的分割方案无影响。所以这个问题可以分治。

枚举所有点，每次选择一个点，$f\left(线段\right)=线段长度+min\left(f\right(选点左侧的线段)+f(选点右侧的线段\left)\right)f(线段)\; =\; 线段长度\; +\; min(f(选点左侧的线段)\; +\; f(选点右侧的线段))$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!)$O(n!)

空间复杂度: 空间复杂度与递归深度相关，所以复杂度为$O\left(n\right)O(n)$O(n)

DFS+记忆化

由题目的样例1，有4种分法

对每种分法的子线段[2],[2,3],[2,3,5],[2,3,5,8],[3,5,8,2],[5,8,2],[8,2],[2], 仍然是一个连续数组的分割，因此实际上所有的分割，都属于$[节点左,节点右][节点左,节点右]$[节点左,节点右]

因此状态数为$O\left(节{点}^2\right)O(节点^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\left(n^2\right)O(n^2)$O(n2)

空间复杂度: 空间复杂度与递归深度和状态数量相关，状态数量其实就是所选的子数组的种类数，所以复杂度为$O\left(n^2\right)O(n^2)$O(n2)