题目描述

Bob 被困在了一个地窖里，他需要破解 n 个锁才能逃出地窖，每一个锁都需要一定的 能量 才能打开。每一个锁需要的能量存放在一个数组 strength 里，其中 strength[i] 表示打开第 i 个锁需要的能量。

Bob 有一把剑，它具备以下的特征：

• 一开始剑的能量为 0 。
• 剑的能量增加因子 X 一开始的值为 1。
• 每分钟，剑的能量都会增加当前的 X 值。
• 打开第 i 把锁，剑的能量需要到达 至少 strength[i]。
• 打开一把锁以后，剑的能量会变回 0，X 的值会增加一个给定的值 K。

你的任务是打开所有 n 把锁并逃出地窖，请你求出需要的 最少 分钟数。

请你返回 Bob 打开所有 n 把锁需要的 最少 时间。

样例

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

输出：4

解释：

无法用少于 4 分钟打开所有的锁，所以答案为 4。

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

输出：5

解释：

无法用少于 5 分钟打开所有的锁，所以答案为 5。

限制

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

算法

(状态压缩动态规划) $O(n \cdot 2^n)$

1. 设状态 $f(mask)$ 表示打开了二进制表示为 $mask$ 的锁所需要的最少时间。
2. 初始时，$f(0) = 0$，其余为 $+\infty$ 待定。
3. 转移时，对于状态 $f(mask)$，枚举一个还没有打开的锁 $i$。打开锁 $i$ 的时间可以通过 $strength(i)$ 和这是第几把需要打开的锁计算出来。转移并更新 $f(mask + 2^i)$。
4. 最终答案为 $f(2^n-1)$。

时间复杂度

• 动态规划的状态数为 $O(2^n)$，转移时间为 $O(n)$，故总时间复杂度为 $O(n \cdot 2^n)$。

空间复杂度

• 需要 $O(2^n)$ 的额外空间存储状态。

C++ 代码

class Solution {
public:
    int findMinimumTime(vector<int>& strength, int K) {
        const int n = strength.size();

        vector<int> f(1 << n, INT_MAX);
        f[0] = 0;

        for (int mask = 0; mask < (1 << n); mask++) {
            int t = __builtin_popcount(mask);

            for (int i = 0; i < n; i++) {
                if ((mask >> i) & 1)
                    continue;

                int nm = mask | 1 << i;
                f[nm] = min(f[nm], f[mask] + (strength[i] - 1) / (1 + t * K) + 1);
            }
        }

        return f[(1 << n) - 1];
    }
};