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& power) { const int n = power.size(); const int maxMask = 1 << n; // dp[i] := min # of days needed to defeat monsters, // where i is the bit representation of monsters vector dp(maxMask, LONG_MAX); dp[0] = 0; for (int mask = 1; mask < maxMask; ++mask) { const int currentGain = __builtin_popcount(mask); for (int i = 0; i < n; ++i) if (mask >> i & 1) dp[mask] = min(dp[mask], dp[mask & ~(1 << i)] + static_cast(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] := min # of days needed to defeat monsters, // where i is the bit representation of 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] := min # Of days needed to defeat monsters, # where i is the bit representation of 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]