杀死所有怪物的最短时间

Submission

运行时间: 1997 ms

内存: 24.6 MB

class Solution:
    def minimumTime(self, power: List[int]) -> int:
        n=len(power)
        dp = {0:0}

        for i in range(n):
            dp_ = {}
            for selects in combinations(range(n), i+1):
                cur = functools.reduce(lambda x,y:x|(1<<y), selects, 0)
                dp_[cur] = min((dp[cur ^ (1<<select)]+ (power[select] + i) // (i+1)) for select in selects)
            dp = dp_


        return max(dp.values())

Explain

这个题解使用了动态规划的策略来求解杀死所有怪物的最短时间。首先，power数组中的每个元素代表每个怪物的力量。算法的核心是使用一个字典dp，其键是一个整数，表示已选择杀死怪物的组合的位掩码，值是完成这个组合所需的最小时间。对于每个可能的组合，它计算了使用不同顺序杀死怪物的成本，并保留了成本最小的时间。这里，每个怪物的杀死时间是怪物的力量除以（已经杀死的怪物数量+1），这反映了随着时间的推移而逐渐增加的能力。动态规划数组在每一步都更新，保存了截至目前为止的所有可能的组合和它们对应的最短完成时间。

时间复杂度: O(n * 2^n)

空间复杂度: O(2^n)


class Solution:
    def minimumTime(self, power: List[int]) -> int:
        n = len(power)
        dp = {0: 0}  # 初始化dp，没有怪物时最短时间为0

        for i in range(n):
            dp_ = {}
            for selects in combinations(range(n), i+1):
                cur = functools.reduce(lambda x, y: x | (1 << y), selects, 0)  # 生成当前选择怪物的位掩码
                dp_[cur] = min((dp[cur ^ (1 << select)] + (power[select] + i) // (i + 1)) for select in selects)  # 计算并更新最小时间
            dp = dp_  # 更新dp为当前计算的dp_

        return max(dp.values())  # 返回最短时间

Explore

位掩码是一种高效的方式来表示组合问题中的状态。在处理如杀死怪物的组合问题时，位掩码通过整数的每个二进制位来表示某个元素是否被选中（例如，怪物是否已被杀死）。这使得状态的转移（即从一个怪物组合到另一个怪物组合的过渡）非常高效，因为它可以通过位运算如AND、OR和XOR来实现。此外，相比于列表或集合，位掩码在空间效率和访问速度上通常有优势，这对于动态规划解法中频繁的状态更新和查询尤为重要。

在`power`数组为空时，代表没有怪物需要被杀死。题解中已经通过初始化`dp = {0: 0}`来处理这种情况，这里`dp[0]`表示没有选择任何怪物时的最短时间为0。因此，如果`power`数组为空，那么在执行动态规划的过程中不会有任何怪物的组合被添加到`dp`中，最终函数会返回`dp[0]`的值，即0。这意味着在没有怪物的情况下，最短时间自然是0分钟。