Question

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 by 1.

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 + 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:
  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)

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;
  }
};

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;
}

Solution 2

class Solution:
  def minimumTime(self, power: List[int]) -> int:
    n = len(power)
    dp = [inf] * (1 << n)
    dp[0] = 0
    for mask in range(1, 1 << n):
      cnt = mask.bit_count()
      for i, v in enumerate(power):
        if (mask >> i) & 1:
          dp[mask] = min(dp[mask], dp[mask ^ (1 << i)] + (v + cnt - 1) // cnt)
    return dp[-1]

class Solution {
  public long minimumTime(int[] power) {
    int n = power.length;
    long[] dp = new long[1 << n];
    Arrays.fill(dp, Long.MAX_VALUE);
    dp[0] = 0;
    for (int mask = 1; mask < 1 << n; ++mask) {
      int cnt = 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)] + (power[i] + cnt - 1) / cnt);
        }
      }
    }
    return dp[(1 << n) - 1];
  }
}

class Solution {
public:
  long long minimumTime(vector<int>& power) {
    int n = power.size();
    vector<long long> dp(1 << n, LONG_MAX);
    dp[0] = 0;
    for (int mask = 1; mask < 1 << n; ++mask) {
      int cnt = __builtin_popcount(mask);
      for (int i = 0; i < n; ++i) {
        if ((mask >> i) & 1) {
          dp[mask] = min(dp[mask], dp[mask ^ (1 << i)] + (power[i] + cnt - 1) / cnt);
        }
      }
    }
    return dp[(1 << n) - 1];
  }
};

func minimumTime(power []int) int64 {
  n := len(power)
  dp := make([]int64, 1<<n)
  for i := range dp {
    dp[i] = math.MaxInt64
  }
  dp[0] = 0
  for mask := 1; mask < 1<<n; mask++ {
    cnt := bits.OnesCount(uint(mask))
    for i, v := range power {
      if ((mask >> i) & 1) == 1 {
        dp[mask] = min(dp[mask], dp[mask^(1<<i)]+int64((v+cnt-1)/cnt))
      }
    }
  }
  return dp[len(dp)-1]
}

function minimumTime(power: number[]): number {
  const n = power.length;
  const dp = new Array(1 << n).fill(Infinity);
  dp[0] = 0;
  for (let mask = 1; mask < 1 << n; ++mask) {
    const cnt = bitCount(mask);
    for (let i = 0; i < n; ++i) {
      if ((mask >> i) & 1) {
        dp[mask] = Math.min(dp[mask], dp[mask ^ (1 << i)] + Math.ceil(power[i] / cnt));
      }
    }
  }
  return dp[dp.length - 1];
}

function bitCount(x) {
  let cnt = 0;
  for (let i = 0; i < 32; ++i) {
    if ((x >> i) & 1) {
      ++cnt;
    }
  }
  return cnt;
}