题解 | #切割成本#

切割成本

http://www.nowcoder.com/practice/5c5fa5bf2a9942fcb1a3844d715087b9

题意

长最大为100000010000001000000的线段上,给n个点。

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

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

其中n<300n<300n<300

方法

递归分治(TLE)

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

表示成图就是

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

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

枚举所有点,每次选择一个点,f(线)=线+min(f(线)+f(线))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(n)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)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(n2)O(n^2)O(n2)

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

全部评论

相关推荐

已老实求offer😫:有点像徐坤(没有冒犯的意思哈)
点赞 评论 收藏
分享
头像
11-07 01:12
重庆大学 Java
精致的小松鼠人狠话不多:签哪了哥
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务