Medium

题目描述

Bob 被困在一个地牢中，必须打破 n 个锁，每个锁都需要一定的能量来打破。每个锁所需的能量存储在一个名为 strength 的数组中，其中 strength[i] 表示打破第 i 个锁所需的能量。

为了打破锁，Bob 使用一把具有以下特性的剑：

  • 剑的初始能量为 0。
  • 剑能量增长的初始因子 x 为 1。
  • 每分钟，剑的能量按当前因子 x 增加。
  • 要打破第 i 个锁，剑的能量必须至少达到 strength[i]。
  • 打破一个锁后，剑的能量重置为 0，因子 x 增加给定值 k。

你的任务是确定 Bob 打破所有 n 个锁并逃出地牢所需的最少时间（以分钟为单位）。

返回 Bob 打破所有 n 个锁所需的最少时间。

示例 1：

输入：strength = [3,4,1], k = 1

输出：4

解释：

时间能量x操作更新后的 x
001无1
111打破第3个锁2
222无2
342打破第2个锁3
433打破第1个锁3

锁无法在少于 4 分钟内被打破，因此答案是 4。

示例 2：

输入：strength = [2,5,4], k = 2

输出：5

约束条件：

  • n == strength.length
  • 1 <= n <= 8
  • 1 <= k <= 10
  • 1 <= strength[i] <= 10^6

提示：

  • 尝试所有 n! 种打破锁的排列方式。

解题思路

这道题是一个经典的状态压缩动态规划问题。由于锁的数量最多只有8个，我们可以用位掩码来表示已经打破的锁的集合。

主要思路：

  1. 状态定义：使用位掩码 mask 表示已经打破的锁的集合，dp[mask] 表示打破 mask 对应的锁集合所需的最少时间。

  2. 状态转移：对于每个状态 mask，我们尝试打破下一个还未打破的锁。假设当前因子为 x，要打破强度为 s 的锁，需要的时间为 ceil(s / x) 分钟。

  3. 因子计算：每打破一个锁后，因子 x 会增加 k。初始因子为 1，打破 cnt 个锁后，因子为 1 + cnt * k。

  4. 优化策略：由于 n 最大为 8，可以通过枚举所有 n! 种排列来找到最优解。但使用动态规划更加高效。

算法流程：

  • 初始化：dp[0] = 0，其他状态为无穷大
  • 遍历所有可能的状态掩码
  • 对于每个状态，尝试打破下一个可能的锁
  • 计算打破该锁所需的时间并更新状态

时间复杂度为 O(2^n * n)，空间复杂度为 O(2^n)，在给定约束下完全可行。

代码实现

class Solution {
public:
    int findMinimumTime(vector<int>& strength, int k) {
        int n = strength.size();
        vector<int> dp(1 << n, INT_MAX);
        dp[0] = 0;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == INT_MAX) continue;
            
            int cnt = __builtin_popcount(mask);
            int x = 1 + cnt * k;
            
            for (int i = 0; i < n; i++) {
                if (!(mask & (1 << i))) {
                    int time = (strength[i] + x - 1) / x;
                    int newMask = mask | (1 << i);
                    dp[newMask] = min(dp[newMask], dp[mask] + time);
                }
            }
        }
        
        return dp[(1 << n) - 1];
    }
};

class Solution:
    def findMinimumTime(self, strength: List[int], k: int) -> int:
        n = len(strength)
        dp = [float('inf')] * (1 << n)
        dp[0] = 0
        
        for mask in range(1 << n):
            if dp[mask] == float('inf'):
                continue
                
            cnt = bin(mask).count('1')
            x = 1 + cnt * k
            
            for i in range(n):
                if not (mask & (1 << i)):
                    time = (strength[i] + x - 1) // x
                    new_mask = mask | (1 << i)
                    dp[new_mask] = min(dp[new_mask], dp[mask] + time)
        
        return dp[(1 << n) - 1]

public class Solution {
    public int FindMinimumTime(IList<int> strength, int k) {
        int n = strength.Count;
        int[] dp = new int[1 << n];
        Array.Fill(dp, int.MaxValue);
        dp[0] = 0;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == int.MaxValue) continue;
            
            int cnt = System.Numerics.BitOperations.PopCount((uint)mask);
            int x = 1 + cnt * k;
            
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) == 0) {
                    int time = (strength[i] + x - 1) / x;
                    int newMask = mask | (1 << i);
                    dp[newMask] = Math.Min(dp[newMask], dp[mask] + time);
                }
            }
        }
        
        return dp[(1 << n) - 1];
    }
}

var findMinimumTime = function(strength, k) {
    const n = strength.length;
    const dp = new Array(1 << n).fill(Infinity);
    dp[0] = 0;
    
    for (let mask = 0; mask < (1 << n); mask++) {
        if (dp[mask]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(2^n × n)需要遍历所有 2^n 个状态，每个状态需要检查 n 个锁
空间复杂度O(2^n)需要存储 2^n 个状态的 dp 数组