Welcome to Subscribe On Youtube
2403. Minimum Time to Kill All Monsters
Description
You are given an integer array power where power[i] is the power of the ith monster.
You start with 0 mana points, and each day you increase your mana points by gain where gain initially is equal to 1.
Each day, after gaining gain mana, you can defeat a monster if your mana points are greater than or equal to the power of that monster. When you defeat a monster:
- your mana points will be reset to
0, and - the value of
gainincreases by1.
Return the minimum number of days needed to defeat all the monsters.
Example 1:
Input: power = [3,1,4] Output: 4 Explanation: The optimal way to beat all the monsters is to: - Day 1: Gain 1 mana point to get a total of 1 mana point. Spend all mana points to kill the 2nd monster. - Day 2: Gain 2 mana points to get a total of 2 mana points. - Day 3: Gain 2 mana points to get a total of 4 mana points. Spend all mana points to kill the 3rd monster. - Day 4: Gain 3 mana points to get a total of 3 mana points. Spend all mana points to kill the 1st monster. It can be proven that 4 is the minimum number of days needed.
Example 2:
Input: power = [1,1,4] Output: 4 Explanation: The optimal way to beat all the monsters is to: - Day 1: Gain 1 mana point to get a total of 1 mana point. Spend all mana points to kill the 1st monster. - Day 2: Gain 2 mana points to get a total of 2 mana points. Spend all mana points to kill the 2nd monster. - Day 3: Gain 3 mana points to get a total of 3 mana points. - Day 4: Gain 3 mana points to get a total of 6 mana points. Spend all mana points to kill the 3rd monster. It can be proven that 4 is the minimum number of days needed.
Example 3:
Input: power = [1,2,4,9] Output: 6 Explanation: The optimal way to beat all the monsters is to: - Day 1: Gain 1 mana point to get a total of 1 mana point. Spend all mana points to kill the 1st monster. - Day 2: Gain 2 mana points to get a total of 2 mana points. Spend all mana points to kill the 2nd monster. - Day 3: Gain 3 mana points to get a total of 3 mana points. - Day 4: Gain 3 mana points to get a total of 6 mana points. - Day 5: Gain 3 mana points to get a total of 9 mana points. Spend all mana points to kill the 4th monster. - Day 6: Gain 4 mana points to get a total of 4 mana points. Spend all mana points to kill the 3rd monster. It can be proven that 6 is the minimum number of days needed.
Constraints:
1 <= power.length <= 171 <= power[i] <= 109
Solutions
Solution 1: State Compression + Memorization Search or Dynamic Programming
Since defeating monsters can increase the daily magic power gain $gain$, the order of defeating monsters affects the result, so we need to enumerate. Noting that the data range of the problem is small, we consider using state compression dynamic programming to solve it.
We define a state $mask$ to represent the current situation of defeating monsters. In its binary representation, $1$ represents the monsters that have been defeated, and $0$ represents the monsters that have not been defeated.
The time complexity is $O(n \times 2^n)$, and the space complexity is $O(2^n)$. Here, $n$ is the number of monsters.
-
class Solution { private int n; private long[] f; private int[] power; public long minimumTime(int[] power) { n = power.length; f = new long[1 << n]; Arrays.fill(f, -1); this.power = power; return dfs(0); } private long dfs(int mask) { if (f[mask] != -1) { return f[mask]; } int cnt = Integer.bitCount(mask); if (cnt == n) { return 0; } long ans = Long.MAX_VALUE; for (int i = 0; i < n; ++i) { if (((mask >> i) & 1) == 1) { continue; } ans = Math.min(ans, dfs(mask | 1 << i) + (power[i] + cnt) / (cnt + 1)); } f[mask] = ans; return ans; } } -
using ll = long long; class Solution { public: vector<ll> f; vector<int> power; int n; long long minimumTime(vector<int>& power) { n = power.size(); f.assign(1 << n, -1); this->power = power; return dfs(0); } ll dfs(int mask) { if (f[mask] != -1) return f[mask]; int cnt = __builtin_popcount(mask); if (cnt == n) return 0; ll ans = LONG_MAX; for (int i = 0; i < n; ++i) { if ((mask >> i) & 1) continue; ans = min(ans, dfs(mask | 1 << i) + (power[i] + cnt) / (cnt + 1)); } f[mask] = ans; return ans; } }; -
class Solution: def minimumTime(self, power: List[int]) -> int: @cache def dfs(mask): cnt = mask.bit_count() if cnt == len(power): return 0 ans = inf for i, v in enumerate(power): if mask & (1 << i): continue ans = min(ans, dfs(mask | 1 << i) + (v + cnt) // (cnt + 1)) return ans return dfs(0) -
func minimumTime(power []int) int64 { n := len(power) f := make([]int64, 1<<n) for i := range f { f[i] = -1 } var dfs func(mask int) int64 dfs = func(mask int) int64 { if f[mask] != -1 { return f[mask] } cnt := bits.OnesCount(uint(mask)) if cnt == n { return 0 } var ans int64 = math.MaxInt64 for i, v := range power { if (mask >> i & 1) == 1 { continue } ans = min(ans, dfs(mask|1<<i)+int64((v+cnt)/(cnt+1))) } f[mask] = ans return ans } return dfs(0) } -
function minimumTime(power: number[]): number { const n = power.length; const f = new Array(1 << n).fill(-1); function dfs(mask) { if (f[mask] != -1) { return f[mask]; } const cnt = bitCount(mask); if (cnt == n) { return 0; } let ans = Infinity; for (let i = 0; i < n; ++i) { if ((mask >> i) & 1) { continue; } ans = Math.min(ans, dfs(mask | (1 << i)) + Math.ceil(power[i] / (cnt + 1))); } f[mask] = ans; return ans; } return dfs(0); } function bitCount(x) { let cnt = 0; for (let i = 0; i < 32; ++i) { if ((x >> i) & 1) { ++cnt; } } return cnt; }