收集巧克力(LeetCode日记)
LeetCode-2735-收集巧克力
题目信息:
给你一个长度为
n
n
n 、下标从
0
0
0 开始的整数数组
n
u
m
s
nums
nums ，表示收集不同巧克力的成本。每个巧克力都对应一个不同的类型，最初，位于下标
i
i
i 的巧克力就对应第
i
i
i 个类型。
在一步操作中，你可以用成本
x
x
x 执行下述行为：
同时修改所有巧克力的类型，将巧克力的类型
i
t
h
i^{th}
ith 修改为类型
(
(
i
+
1
)
m
o
d
n
)
t
h
((i + 1) mod n)^{th}
((i+1)modn)th。
假设你可以执行任意次操作，请返回收集所有类型巧克力所需的最小成本。
- 示例1：
输入：nums = [20,1,15], x = 5
输出：13
解释：最开始，巧克力的类型分别是 [0,1,2] 。我们可以用成本 1 购买第 1 个类型的巧克力。
接着，我们用成本 5 执行一次操作，巧克力的类型变更为 [1,2,0] 。我们可以用成本 1 购买第 2 个类型的巧克力。
然后，我们用成本 5 执行一次操作，巧克力的类型变更为 [2,0,1] 。我们可以用成本 1 购买第 0 个类型的巧克力。
因此，收集所有类型的巧克力需要的总成本是 (1 + 5 + 1 + 5 + 1) = 13 。可以证明这是一种最优方案。
- 示例2：
输入：nums = [1,2,3], x = 4
输出：6
解释：我们将会按最初的成本收集全部三个类型的巧克力，而不需执行任何操作。因此，收集所有类型的巧克力需要的总成本是 1 + 2 + 3 = 6 。
提示：
- 1 <= nums.length <= 1000
- 1 <= nums[i] <= 109
- 1 <= x <= 109
相关标签 ：数组、枚举、动态规划
题解
今天的问题属于中等难度，初见这道题，我认为动态规划将是一个很好的思路。对于每次操做，都可以比较当前情况下，直接收集权值最小的蛋糕 或者 先进行操做在进行购买权值最小的蛋糕。可是尝试后发现这样并不成功。下面我们来看一下正确的方法。
方法：枚举收集的次数
对于初始类型为
i
i
i 的巧克力，如果我们一共进行了
k
k
k
kkk
kkk 次操作，相当于我们可以用：
n
u
m
s
[
i
]
,
n
u
m
s
[
(
i
+
1
)
m
o
d
n
]
,
⋯
,
n
u
m
s
[
(
i
+
k
)
m
o
d
n
]
(
1
)
nums[i],nums[(i+1)modn],⋯,nums[(i+k)modn] (1)
nums[i],nums[(i+1)modn],⋯,nums[(i+k)modn] (1)
中的任意成本去购买它。由于我们希望成本最小，那么我们一定选择上述
k
+
1
k+1
k+1 个成本中的最小值。同时我们发现，当进行了第
n
n
n 次操作后，它的价格又会回到
n
u
m
s
[
i
]
nums[i]
nums[i] 并继续开始循环，因此操作的次数不会超过
n
−
1
n−1
n−1 。
这样一来，我们就可以枚举操作次数了，它的范围为
[
0
,
n
−
1
]
[0,n−1]
[0,n−1] 。当操作次数为
k
k
k 时，初始类型为
i
i
i 的巧克力需要的成本就是
(
1
)
(1)
(1) 中的最小值，我们就可以使用一个二维数组
f
(
i
,
k
)
f(i,k)
f(i,k) 记录该值，它有如下的递推式：
{
f
(
i
,
0
)
=
n
u
m
s
[
i
]
f
(
i
,
k
)
=
min
{
f
(
i
,
k
−
1
)
,
n
u
m
s
[
(
i
+
k
)
m
o
d
n
]
}
left{begin{array}{l}f(i, 0)=n u m s[i] \f(i, k)=min {f(i, k-1), n u m s[(i+k) bmod n]}end{array}right.
{f(i,0)=nums[i]f(i,k)=min{f(i,k−1),nums[(i+k)modn]}
即
f
(
i
,
k
)
f(i,k)
f(i,k) 相较于
f
(
i
,
k
−
1
)
f(i,k−1)
f(i,k−1) ，多了一个
n
u
m
s
[
(
i
+
k
)
m
o
d
n
]
nums[(i+k) mod n]
nums[(i+k) mod n] 的选择。此时，操作次数为
k
k
k 时的最小成本即为：
k
⋅
x
+
∑
i
=
0
n
−
1
f
(
i
,
k
)
(
2
)
k cdot x+sum_{i=0}^{n-1} f(i, k) (2)
k⋅x+i=0∑n−1f(i,k) (2)
最终的答案即为所有
k
∈
[
0
,
n
−
1
]
k∈[0,n−1]
k∈[0,n−1] 中式
(
2
)
(2)
(2) 的最小值。
实现代码（Python）
class Solution:
def minCost(self, nums: List[int], x: int) -> int:
n = len(nums)
f = nums[:] # 初始化 f 数组，表示当前位置开始的最小成本
ans = sum(f) # 初始化结果为 f 的总和
for k in range(1, n):
# 更新 f 数组，每次将当前位置的值更新为当前位置和右侧位置的最小值
for i in range(n):
f[i] = min(f[i], nums[(i + k) % n])
# 更新结果，计算当前成本并加上操作次数乘以 x
ans = min(ans, k * x + sum(f))
return ans
复杂度分析：
- 时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)。 - 空间复杂度：
O
(
n
)
O(n)
O(n) 。
题记：
- 研究生在读，我会尽量保持LeetCode每日一题的思路和代码输出。希望大家多多支持。
- 水平有限，希望各位大佬能够批评指正。您的教诲是我进步的船帆。
- 希望各位跟我一样的小白能跟我一起参与到做题和讨论中来。共同进步是我所能期盼的最高愿想。
- 您的点赞和关注是我坚持分享的动力泉源，希望能将这件简单平凡的事一直做下去。感谢大家。