Skip to content

2403. Minimum Time to Kill All Monsters 👍

  • Time: $O(2^n \cdot n)$
  • Space: $O(2^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  long long minimumTime(vector<int>& power) {
    const int n = power.size();
    const int maxMask = 1 << n;
    // dp[i] := the minimum number of days needed to defeat the monsters, where
    // i is the bitmask of the monsters
    vector<long> dp(maxMask, LONG_MAX);
    dp[0] = 0;

    for (unsigned mask = 1; mask < maxMask; ++mask) {
      const int currentGain = popcount(mask);
      for (int i = 0; i < n; ++i)
        if (mask >> i & 1)
          dp[mask] =
              min(dp[mask],
                  dp[mask & ~(1 << i)] +
                      static_cast<int>(ceil(power[i] * 1.0 / currentGain)));
    }

    return dp.back();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public long minimumTime(int[] power) {
    final int n = power.length;
    final int maxMask = 1 << n;
    // dp[i] := the minimum number of days needed to defeat the monsters, where
    // i is the bitmask of the monsters
    long[] dp = new long[maxMask];
    Arrays.fill(dp, Long.MAX_VALUE);
    dp[0] = 0;

    for (int mask = 1; mask < maxMask; ++mask) {
      final int currentGain = Integer.bitCount(mask);
      for (int i = 0; i < n; ++i)
        if ((mask >> i & 1) == 1)
          dp[mask] = Math.min(dp[mask], dp[mask & ~(1 << i)] +
                                            (int) (Math.ceil(power[i] * 1.0 / currentGain)));
    }

    return dp[maxMask - 1];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def minimumTime(self, power: list[int]) -> int:
    n = len(power)
    maxMask = 1 << n
    # dp[i] := the minimum number of days needed to defeat the monsters, where
    # i is the bitmask of the monsters
    dp = [math.inf] * maxMask
    dp[0] = 0

    for mask in range(1, maxMask):
      currentGain = mask.bit_count()
      for i in range(n):
        if mask >> i & 1:
          dp[mask] = min(dp[mask], dp[mask & ~(1 << i)] +
                         int(math.ceil(power[i] / currentGain)))

    return dp[-1]