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$.
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|