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
gain
increases 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 <= 17
1 <= power[i] <= 109
Solutions
Solution 1: State Compression + Memoization Search
We note that the number of monsters is at most $17$, which means we can use a 17-bit binary number to represent the state of the monsters. The $i$-th bit being $1$ indicates that the $i$-th monster is still alive, and $0$ indicates that the $i$-th monster has been defeated.
We design a function $\textit{dfs}(\textit{mask})$ to represent the minimum number of days needed to defeat all monsters when the current state of the monsters is $\textit{mask}$. The answer is $\textit{dfs}(2^n - 1)$, where $n$ is the number of monsters.
The calculation of the function $\textit{dfs}(\textit{mask})$ is as follows:
- If $\textit{mask} = 0$, it means all monsters have been defeated, return $0$;
- Otherwise, we enumerate each monster $i$. If the $i$-th monster is still alive, we can choose to defeat the $i$-th monster, then recursively calculate $\textit{dfs}(\textit{mask} \oplus 2^i)$, and update the answer to $\textit{ans} = \min(\textit{ans}, \textit{dfs}(\textit{mask} \oplus 2^i) + \lceil \frac{x}{\textit{gain}} \rceil)$, where $x$ is the strength of the $i$-th monster, and $\textit{gain} = 1 + (n - \textit{mask}.\textit{bit_count}())$ represents the current daily mana gain.
Finally, we return $\textit{dfs}(2^n - 1)$.
The time complexity is $O(2^n \times n)$, and the space complexity is $O(2^n)$. Here, $n$ is the number of monsters.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
|
Solution 2: State Compression + Dynamic Programming
We can convert the memoization search in Solution 1 to dynamic programming. Define $f[\textit{mask}]$ to represent the minimum number of days needed to defeat all monsters when the current state of the monsters is $\textit{mask}$. Here, $\textit{mask}$ is an $n$-bit binary number, where the $i$-th bit being $1$ indicates that the $i$-th monster has been defeated, and $0$ indicates that the $i$-th monster is still alive. Initially, $f[0] = 0$, and the rest $f[\textit{mask}] = +\infty$. The answer is $f[2^n - 1]$.
We enumerate $\textit{mask}$ in the range $[1, 2^n - 1]$. For each $\textit{mask}$, we enumerate each monster $i$. If the $i$-th monster is defeated, it can be transferred from the previous state $\textit{mask} \oplus 2^i$, with a transfer cost of $(\textit{power}[i] + \textit{gain} - 1) / \textit{gain}$, where $\textit{gain} = \textit{mask}.\textit{bitCount}()$.
Finally, return $f[2^n - 1]$.
The time complexity is $O(2^n \times n)$, and the space complexity is $O(2^n)$. Here, $n$ is the number of monsters.
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|