#3500

Minimum Cost to Divide Array Into Subarrays

international master · 2045 · lc hard +32 · 27.7% accepted · 84 likes · top 6%

Description

Given arrays nums and cost of equal length and integer k, partition nums into contiguous subarrays. For the i-th subarray covering nums[l..r] (1-indexed), its cost is:

- (prefix_sum[r] + k * i) * sum(cost[l..r])

where prefix_sum[r] is the sum of the first r+1 elements of nums.

Return the minimum total cost over all valid partitions.

Code

1

2

3

class Solution:
    def minimumCost(self, nums: List[int], cost: List[int], k: int) -> int:

class Solution:
    def minimumCost(self, nums: List[int], cost: List[int], k: int) -> int: