[Leetcode] 2735. Collecting Chocolates (Medium)

概述

題目

https://leetcode.com/problems/collecting-chocolates/
給定一數組表是巧克力的成本，透過每次多付出 x 成本進行輪轉，可讓巧克力的成本轉換，試問取得所有巧克力的最少成本為何

心得

週賽時題目說明有問題、範例也是錯的，然後又一臉 DP 樣，最終放棄；後來回看確實負評也 >> 正評

另類 DP

思路

from LarryNY，照樣輪轉一次，比較每個巧克力在不同轉輪次數下的成本最低為何，最終求得 min 結果

程式

class Solution(object):
    def minCost(self, nums, x):
        """
        :type nums: List[int]
        :type x: int
        :rtype: int
        """
        n = len(nums)
        arr = [c for c in nums]
        mnv = sum(nums)

        for i in range(n):
            cur = i*x
            for j in range(n):
                arr[j] = min(arr[j], nums[(j+i)%n])
            mnv = min(mnv, sum(arr) + cur)
            
        return mnv

from lee215 大神

class Solution(object):
    def minCost(self, nums, x):
        """
        :type nums: List[int]
        :type x: int
        :rtype: int
        """
        n = len(nums)
        arr = [x*i for i in range(n)]

        for i in range(n):
            cur = nums[i]
            for j in range(n):
                cur = min(cur, nums[i-j])
                arr[j] += cur
        return min(arr)