3500-MinimumCostToDivideArrayIntoSubarrays.go

package main

// 3500. Minimum Cost to Divide Array Into Subarrays
// You are given two integer arrays, nums and cost, of the same size, and an integer k.

// You can divide nums into subarrays. 
// The cost of the ith subarray consisting of elements nums[l..r] is:
//     (nums[0] + nums[1] + ... + nums[r] + k * i) * (cost[l] + cost[l + 1] + ... + cost[r]).

// Note that i represents the order of the subarray: 1 for the first subarray, 2 for the second, and so on.

// Return the minimum total cost possible from any valid division.

// A subarray is a contiguous non-empty sequence of elements within an array.

// Example 1:
// Input: nums = [3,1,4], cost = [4,6,6], k = 1
// Output: 110
// Explanation:
// The minimum total cost possible can be achieved by dividing nums into subarrays [3, 1] and [4].
// The cost of the first subarray [3,1] is (3 + 1 + 1 * 1) * (4 + 6) = 50.
// The cost of the second subarray [4] is (3 + 1 + 4 + 1 * 2) * 6 = 60.

// Example 2:
// Input: nums = [4,8,5,1,14,2,2,12,1], cost = [7,2,8,4,2,2,1,1,2], k = 7
// Output: 985
// Explanation:
// The minimum total cost possible can be achieved by dividing nums into subarrays [4, 8, 5, 1], [14, 2, 2], and [12, 1].
// The cost of the first subarray [4, 8, 5, 1] is (4 + 8 + 5 + 1 + 7 * 1) * (7 + 2 + 8 + 4) = 525.
// The cost of the second subarray [14, 2, 2] is (4 + 8 + 5 + 1 + 14 + 2 + 2 + 7 * 2) * (2 + 2 + 1) = 250.
// The cost of the third subarray [12, 1] is (4 + 8 + 5 + 1 + 14 + 2 + 2 + 12 + 1 + 7 * 3) * (1 + 2) = 210.

// Constraints:
//     1 <= nums.length <= 1000
//     cost.length == nums.length
//     1 <= nums[i], cost[i] <= 1000
//     1 <= k <= 1000

import "fmt"

func minimumCost(nums []int, cost []int, k int) int64 {
    n := len(nums)
    if n == 0 { return 0 }
    // 计算前缀和
    pn, pc := make([]int64, n), make([]int64, n)
    pn[0], pc[0] = int64(nums[0]), int64(cost[0])
    for i := 1; i < n; i++ {
        pn[i], pc[i] = pn[i-1] + int64(nums[i]), pc[i-1] + int64(cost[i])
    }
    dp := make([][]int64, n)
    for i := range dp {
        dp[i] = make([]int64, n)
        for j := range dp[i] {
            dp[i][j] = -1
        }
    }
    var find func(int, int) int64
    find = func(s, e int) int64 {
        if dp[s][e] != -1 { return dp[s][e] }
        // 计算当前区间的nums和 & 计算当前区间的cost和（注意这里的逻辑与Java代码一致，取从s到末尾的总和，而非e）
        sumN, sumC := int64(0), int64(0)
        if s == 0 {
            sumN, sumC = pn[e], pc[n - 1] // 整个数组的cost总和
        } else {
            sumN, sumC = pn[e] - pn[s-1],  pc[n-1] - pc[s-1] // 从s到末尾的总和
        }
        res := (sumN + int64(k)) * sumC
        if e == n - 1 {
            dp[s][e] = res
            return res
        }
        // 分割的情况：当前区间结束于e，后面处理e+1
        option1 := res + find(e + 1, e + 1)
        // 不分割，继续扩展当前区间到e+1
        option2 := find(s, e + 1)
        if option1 < option2 {
            dp[s][e] = option1
        } else {
            dp[s][e] = option2
        }
        return dp[s][e]
    }
    return find(0, 0)
}

func minimumCost1(nums []int, cost []int, k int) int64 {
    n, m := len(nums), len(cost)
    dp, suffixSumCost,prefixSumNum, prefixSumCost := make([]int64, n), make([]int64, n) ,make([]int64, n), make([]int64, n)
    prefixSumNum[0], prefixSumCost[0] = int64(nums[0]), int64(cost[0])
    for i := 1; i < n; i += 1 {
        prefixSumNum[i] = prefixSumNum[i - 1] + int64(nums[i])
        prefixSumCost[i] = prefixSumCost[i - 1] + int64(cost[i])
    }
    suffixSumCost[m - 1] = int64(cost[m - 1])
    for i := m - 2; i >= 0; i-- {
        suffixSumCost[i] = suffixSumCost[i + 1] + int64(cost[i])
    }
    min := func (x, y int64) int64 { if x < y { return x; }; return y; }
    for i := 0; i < n; i++ {
        dp[i] = prefixSumNum[i] * prefixSumCost[i] + int64(k) * (suffixSumCost[0])
        for j := 0; j < i; j++ {
            dp[i] = min(
                dp[i], 
                dp[j] + prefixSumNum[i] * (prefixSumCost[i] - prefixSumCost[j]) + int64(k) * suffixSumCost[j + 1],
            )
        }
    }
    return dp[n -1 ]
}

func main() {
    // Example 1:
    // Input: nums = [3,1,4], cost = [4,6,6], k = 1
    // Output: 110
    // Explanation:
    // The minimum total cost possible can be achieved by dividing nums into subarrays [3, 1] and [4].
    // The cost of the first subarray [3,1] is (3 + 1 + 1 * 1) * (4 + 6) = 50.
    // The cost of the second subarray [4] is (3 + 1 + 4 + 1 * 2) * 6 = 60.
    fmt.Println(minimumCost([]int{3,1,4}, []int{4,6,6}, 1)) // 110
    // Example 2:
    // Input: nums = [4,8,5,1,14,2,2,12,1], cost = [7,2,8,4,2,2,1,1,2], k = 7
    // Output: 985
    // Explanation:
    // The minimum total cost possible can be achieved by dividing nums into subarrays [4, 8, 5, 1], [14, 2, 2], and [12, 1].
    // The cost of the first subarray [4, 8, 5, 1] is (4 + 8 + 5 + 1 + 7 * 1) * (7 + 2 + 8 + 4) = 525.
    // The cost of the second subarray [14, 2, 2] is (4 + 8 + 5 + 1 + 14 + 2 + 2 + 7 * 2) * (2 + 2 + 1) = 250.
    // The cost of the third subarray [12, 1] is (4 + 8 + 5 + 1 + 14 + 2 + 2 + 12 + 1 + 7 * 3) * (1 + 2) = 210.
    fmt.Println(minimumCost([]int{4,8,5,1,14,2,2,12,1}, []int{7,2,8,4,2,2,1,1,2}, 7)) // 985

    fmt.Println(minimumCost([]int{1,2,3,4,5,6,7,8,9}, []int{1,2,3,4,5,6,7,8,9}, 1)) // 1350
    fmt.Println(minimumCost([]int{1,2,3,4,5,6,7,8,9}, []int{9,8,7,6,5,4,3,2,1}, 1)) // 642
    fmt.Println(minimumCost([]int{9,8,7,6,5,4,3,2,1}, []int{1,2,3,4,5,6,7,8,9}, 1)) // 1901
    fmt.Println(minimumCost([]int{9,8,7,6,5,4,3,2,1}, []int{9,8,7,6,5,4,3,2,1}, 1)) // 1320

    fmt.Println(minimumCost1([]int{3,1,4}, []int{4,6,6}, 1)) // 110
    fmt.Println(minimumCost1([]int{4,8,5,1,14,2,2,12,1}, []int{7,2,8,4,2,2,1,1,2}, 7)) // 985
    fmt.Println(minimumCost1([]int{1,2,3,4,5,6,7,8,9}, []int{1,2,3,4,5,6,7,8,9}, 1)) // 1350
    fmt.Println(minimumCost1([]int{1,2,3,4,5,6,7,8,9}, []int{9,8,7,6,5,4,3,2,1}, 1)) // 642
    fmt.Println(minimumCost1([]int{9,8,7,6,5,4,3,2,1}, []int{1,2,3,4,5,6,7,8,9}, 1)) // 1901
    fmt.Println(minimumCost1([]int{9,8,7,6,5,4,3,2,1}, []int{9,8,7,6,5,4,3,2,1}, 1)) // 1320
}