收集巧克力(LeetCode日记)

发布时间:2023年12月28日

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=0n?1?f(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每日一题的思路和代码输出。希望大家多多支持。
  • 水平有限,希望各位大佬能够批评指正。您的教诲是我进步的船帆。
  • 希望各位跟我一样的小白能跟我一起参与到做题和讨论中来。共同进步是我所能期盼的最高愿想。
  • 您的点赞和关注是我坚持分享的动力泉源,希望能将这件简单平凡的事一直做下去。感谢大家。
文章来源:https://blog.csdn.net/weixin_52242569/article/details/135270149
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。