2023.12.28力扣每日一题——收集巧克力

题目来源

力扣每日一题；题序：2735

我的题解（参考力扣官方题解）

嗯……今天不会，就当一次搬运工吧。

方法一 枚举

对于初始类型为 iii 的巧克力，如果一共进行了 k次操作，相当于可以用：
nums[i],nums[(i+1) mod n],⋯ ,nums[(i+k)  mod  n] (1)
中的任意成本去购买它。由于希望成本最小，那么我们一定选择上述 k+1 个成本中的最小值。同时发现，当进行了第 n次操作后，它的价格又会回到 nums[i]并继续开始循环，因此操作的次数不会超过 n−1。
这样一来，就可以枚举操作次数了，它的范围为 [0,n−1]。当操作次数为 k 时，初始类型为 iii 的巧克力需要的成本就是 (1)中的最小值，就可以使用一个二维数组 f(i,k)记录该值，它有如下的递推式：

即 f(i,k) 相较于 f(i,k−1)，多了一个 nums[(i+k) mod n] 的选择。此时，操作次数为 kkk 时的最小成本即为：

最终的答案即为所有 k∈[0,n−1] 中式 (2) 的最小值。
注意到 f(i,k) 只与 f(i,k−1) 有关，那么我们可以省去 k的这一维度，减少空间复杂度。

时间复杂度： O($n^2$)
空间复杂度：O(n)

class Solution {
    public long minCost(int[] nums, int x) {
        int n = nums.length;
        int[] f = new int[n];
        System.arraycopy(nums, 0, f, 0, n);
        long ans = getSum(f);
        for (int k = 1; k < n; ++k) {
            for (int i = 0; i < n; ++i) {
                f[i] = Math.min(f[i], nums[(i + k) % n]);
            }
            ans = Math.min(ans, (long) k * x + getSum(f));
        }
        return ans;
    }

    public long getSum(int[] f) {
        long sum = 0;
        for (int num : f) {
            sum += num;
        }
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

方法二 二次差分

看官方题解，主要是自己都没看懂，哈哈哈

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈