Question

2735. Collecting Chocolates

中文文档

Description

You are given a 0-indexed integer array nums of size n representing the cost of collecting different chocolates. The cost of collecting the chocolate at the index i is nums[i]. Each chocolate is of a different type, and initially, the chocolate at the index i is of ith type.

In one operation, you can do the following with an incurred cost of x:

• Simultaneously change the chocolate of ith type to ((i + 1) mod n)th type for all chocolates.

Return _the minimum cost to collect chocolates of all types, given that you can perform as many operations as you would like._

 

Example 1:

Input: nums = [20,1,15], x = 5
Output: 13
Explanation: Initially, the chocolate types are [0,1,2]. We will buy the 1st type of chocolate at a cost of 1.
Now, we will perform the operation at a cost of 5, and the types of chocolates will become [1,2,0]. We will buy the 2nd type of chocolate at a cost of 1.
Now, we will again perform the operation at a cost of 5, and the chocolate types will become [2,0,1]. We will buy the 0th type of chocolate at a cost of 1. 
Thus, the total cost will become (1 + 5 + 1 + 5 + 1) = 13. We can prove that this is optimal.

Example 2:

Input: nums = [1,2,3], x = 4
Output: 6
Explanation: We will collect all three types of chocolates at their own price without performing any operations. Therefore, the total cost is 1 + 2 + 3 = 6.

 

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 109
• 1 <= x <= 109

Solutions

Solution 1: Enumeration

We consider enumerating the number of operations, and define $f[i][j]$ as the minimum cost after the $i$-th chocolate has undergone $j$ operations.

For the $i$-th chocolate:

• If $j = 0$, i.e., no operation is performed, then $f[i][j] = nums[i]$.
• If $0 < j \leq n-1$, its minimum cost is the minimum cost within the index range $[i,.. (i - j + n) \bmod n]$, i.e., $f[i][j] = \min{nums[i], nums[i - 1], \cdots, nums[(i - j + n) \bmod n]}$, or it can be written as $f[i][j] = \min{f[i][j - 1], nums[(i - j + n) \bmod n]}$.
• If $j \ge n$, since when $j = n - 1$, all minimum costs have been covered, if $j$ continues to increase, the minimum cost will not change, but the increase in the number of operations will lead to an increase in the final cost, so we do not need to consider the case where $j \ge n$.

In summary, we can get the state transition equation:

$$ f[i][j] = \begin{cases} nums[i] ,& j = 0 \ \min(f[i][j - 1], nums[(i - j + n) \bmod n]) ,& 0 \lt j \leq n - 1 \end{cases} $$

Finally, we only need to enumerate the number of operations $j$, calculate the minimum cost under each number of operations, and take the minimum value. That is, the answer is $\min\limits_{0 \leq j \leq n - 1} \sum\limits_{i = 0}^{n - 1} f[i][j] + x \times j$.

The time complexity is $O(n^2)$, and the space complexity is $O(n^2)$. Where $n$ is the length of the array $nums$.

class Solution:
  def minCost(self, nums: List[int], x: int) -> int:
    n = len(nums)
    f = [[0] * n for _ in range(n)]
    for i, v in enumerate(nums):
      f[i][0] = v
      for j in range(1, n):
        f[i][j] = min(f[i][j - 1], nums[(i - j) % n])
    return min(sum(f[i][j] for i in range(n)) + x * j for j in range(n))

class Solution {
  public long minCost(int[] nums, int x) {
    int n = nums.length;
    int[][] f = new int[n][n];
    for (int i = 0; i < n; ++i) {
      f[i][0] = nums[i];
      for (int j = 1; j < n; ++j) {
        f[i][j] = Math.min(f[i][j - 1], nums[(i - j + n) % n]);
      }
    }
    long ans = 1L << 60;
    for (int j = 0; j < n; ++j) {
      long cost = 1L * x * j;
      for (int i = 0; i < n; ++i) {
        cost += f[i][j];
      }
      ans = Math.min(ans, cost);
    }
    return ans;
  }
}

class Solution {
public:
  long long minCost(vector<int>& nums, int x) {
    int n = nums.size();
    int f[n][n];
    for (int i = 0; i < n; ++i) {
      f[i][0] = nums[i];
      for (int j = 1; j < n; ++j) {
        f[i][j] = min(f[i][j - 1], nums[(i - j + n) % n]);
      }
    }
    long long ans = 1LL << 60;
    for (int j = 0; j < n; ++j) {
      long long cost = 1LL * x * j;
      for (int i = 0; i < n; ++i) {
        cost += f[i][j];
      }
      ans = min(ans, cost);
    }
    return ans;
  }
};

func minCost(nums []int, x int) int64 {
  n := len(nums)
  f := make([][]int, n)
  for i, v := range nums {
    f[i] = make([]int, n)
    f[i][0] = v
    for j := 1; j < n; j++ {
      f[i][j] = min(f[i][j-1], nums[(i-j+n)%n])
    }
  }
  ans := 1 << 60
  for j := 0; j < n; j++ {
    cost := x * j
    for i := 0; i < n; i++ {
      cost += f[i][j]
    }
    ans = min(ans, cost)
  }
  return int64(ans)
}

function minCost(nums: number[], x: number): number {
  const n = nums.length;
  const f: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
  for (let i = 0; i < n; ++i) {
    f[i][0] = nums[i];
    for (let j = 1; j < n; ++j) {
      f[i][j] = Math.min(f[i][j - 1], nums[(i - j + n) % n]);
    }
  }
  let ans = Infinity;
  for (let j = 0; j < n; ++j) {
    let cost = x * j;
    for (let i = 0; i < n; ++i) {
      cost += f[i][j];
    }
    ans = Math.min(ans, cost);
  }
  return ans;
}

impl Solution {
  pub fn min_cost(nums: Vec<i32>, x: i32) -> i64 {
    let n = nums.len();
    let mut f = vec![vec![0; n]; n];
    for i in 0..n {
      f[i][0] = nums[i];
      for j in 1..n {
        f[i][j] = f[i][j - 1].min(nums[(i - j + n) % n]);
      }
    }
    let mut ans = i64::MAX;
    for j in 0..n {
      let mut cost = (x as i64) * (j as i64);
      for i in 0..n {
        cost += f[i][j] as i64;
      }
      ans = ans.min(cost);
    }
    ans
  }
}