We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Divide Array Into Subarrays

Number: 3765

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given two arrays, nums and cost, of equal length and an integer k, you must partition the array nums into one or more contiguous subarrays. The twist is that the cost to “pay” for each chosen subarray depends on two parts: a global prefix sum of nums up to the current subarray’s end (plus an additional k multiplied by the order/index of the subarray) and the sum of the cost values for only that subarray. Formally, if the i‑th subarray spans indices l to r, its cost is computed as (nums[0] + nums[1] + ... + nums[r] + k * i) multiplied by (cost[l] + cost[l + 1] + … + cost[r]). The task is to choose a division of the array that minimizes the total cost summed over all subarrays.

Key Insights

  • The cost of any subarray [l, r] depends on a fixed “global” prefix sum of nums (from index 0 to r) combined with the order of the subarray.
  • Precomputing prefix sums for both nums and cost allows quick computation of any required interval sum.
  • The decision of where to split affects both the subarray’s own cost (through the cost sum) and the global prefix sum part—hinting toward a dynamic programming solution.
  • A state can be defined by the ending index and the number of subarrays (or order) used, and then the solution is recovered by taking the minimum over all allowable partitions.
  • Although a straightforward DP approach may lead to cubic time complexity (O(n^3)), techniques such as convex hull trick or other optimizations can reduce it given the “linearity” hidden in parts of the recurrence.

Space and Time Complexity

Time Complexity: O(n^2) with optimization (the naïve solution is O(n^3) but can be optimized using techniques such as convex hull optimization) Space Complexity: O(n^2)

Solution

We solve the problem by defining a DP state dp[m][r] where m represents the number of subarrays formed and r is the ending index of the array used. For a subarray spanning indices l to r that is the m‑th subarray, its cost is computed as:   cost(l, r, m) = (prefix_nums[r] + k * m) * (prefix_cost[r] – (l > 0 ? prefix_cost[l-1] : 0)) For m = 1 (only one subarray), we have:   dp[1][r] = (prefix_nums[r] + k) * prefix_cost[r] For m > 1, we try every possible split position l (where the m‑th subarray starts at l and ends at r) and update:   dp[m][r] = min for all l in [m-1, r] { dp[m-1][l-1] + cost(l, r, m) } Finally, the answer is the minimum dp[m][n-1] over all m between 1 and n. The trick here is to use the precomputed prefix sums (prefix_nums and prefix_cost) so that the cost for any subarray [l, r] is computed in constant time. This DP formulation naturally highlights the trade off between making many cuts (increasing m and thus the additional k * m factor) and fewer cuts (resulting in cost sums that might be larger).

Code Solutions

# Python solution with detailed comments

def minCostDivideArray(nums, cost, k):
    n = len(nums)
    # Precompute prefix sums for nums and cost arrays.
    prefix_nums = [0] * n
    prefix_cost = [0] * n
    prefix_nums[0] = nums[0]
    prefix_cost[0] = cost[0]
    for i in range(1, n):
        prefix_nums[i] = prefix_nums[i - 1] + nums[i]
        prefix_cost[i] = prefix_cost[i - 1] + cost[i]
    
    # dp[m][r]: using m partitions (subarrays) ending at index r.
    # We use a large number for initialization.
    INF = 10**18
    dp = [[INF] * n for _ in range(n + 1)]
    
    # Base case: when there is only one subarray.
    for r in range(n):
        dp[1][r] = (prefix_nums[r] + k) * prefix_cost[r]
    
    # Fill the DP table for m >= 2 partitions.
    for m in range(2, n + 1):
        # r must be at least m-1 to allow m subarrays.
        for r in range(m - 1, n):
            # Try all possible starting positions l for the last subarray.
            for l in range(m - 1, r + 1):
                # Calculate cost for subarray [l, r] when it is the mth subarray.
                cost_subarray = (prefix_nums[r] + k * m) * (prefix_cost[r] - (prefix_cost[l - 1] if l > 0 else 0))
                # If l == 0, we cannot have m > 1 subarray so skip.
                if l == 0:
                    continue
                dp[m][r] = min(dp[m][r], dp[m - 1][l - 1] + cost_subarray)
    
    # The answer is the minimum cost over all possible numbers of subarrays.
    ans = INF
    for m in range(1, n + 1):
        ans = min(ans, dp[m][n - 1])
    
    return ans

# Example Usage:
if __name__ == "__main__":
    nums1 = [3, 1, 4]
    cost1 = [4, 6, 6]
    k1 = 1
    print(minCostDivideArray(nums1, cost1, k1))  # Expected output: 110
← Back to All Questions