2025-09-24：将数组分割为子数组的最小代价。用go语言，给定两个等长的整数数组 nums 和 cost，以及一个整数 k

2025-09-24：将数组分割为子数组的最小代价。用go语言，给定两个等长的整数数组 nums 和 cost，以及一个整数 k。把 nums 按原顺序划分成若干个不为空且相互连贯的区间（子数组），记第 j 个区间为覆盖索引 l..r 的那一段。该区间对总体代价的贡献为：

（nums 从开头到 r 的前缀和 + k × j）乘以（cost 在 l..r 上的和）。

也就是说，第 j 段的权重是 prefixNums[r] + k*j，其中 prefixNums[r]=sum_{t=0}^{r} nums[t]，乘以该段 cost 的累加和。所有分段的贡献相加得到总代价。要求在所有合法分割方式中选出能使总代价最小的一种，并返回该最小值。

1 <= nums.length <= 1000。

cost.length == nums.length。

1 <= nums[i], cost[i] <= 1000。

1 <= k <= 1000。

输入： nums = [4,8,5,1,14,2,2,12,1], cost = [7,2,8,4,2,2,1,1,2], k = 7。

输出： 985。

解释：

将 nums 分割为子数组 [4, 8, 5, 1] ，[14, 2, 2] 和 [12, 1] ，得到最小总代价。

第一个子数组 [4, 8, 5, 1] 的代价是 (4 + 8 + 5 + 1 + 7 * 1) * (7 + 2 + 8 + 4) = 525。

第二个子数组 [14, 2, 2] 的代价是 (4 + 8 + 5 + 1 + 14 + 2 + 2 + 7 * 2) * (2 + 2 + 1) = 250。

第三个子数组 [12, 1] 的代价是 (4 + 8 + 5 + 1 + 14 + 2 + 2 + 12 + 1 + 7 * 3) * (1 + 2) = 210。

题目来自力扣3500。

好的，我们先一步步理清这个问题的计算逻辑，然后分析代码的算法思路，最后给出复杂度。

1. 问题重述

我们有：

• • nums 数组，长度 n
• • cost 数组，长度 n
• • 整数 k

分割规则：

• • 必须保持 nums 原顺序，分割成若干连续非空子数组。
• • 第 j 个子数组（从 1 开始编号）覆盖索引 l..r（0-based）。
• • 该段的代价 = (prefixNums[r] + k * j) * sum(cost[l..r])
• • 其中 prefixNums[r] = nums[0] + nums[1] + ... + nums[r]
• • 总代价 = 所有段的代价之和。

目标：最小化总代价。

2. 代价公式的变形

设：

• • P[i] = nums[0] + ... + nums[i-1]（前缀和，P[0]=0，P[1]=nums[0]，等等）
• • S[i] = cost[0] + ... + cost[i-1]（cost 的前缀和）

如果第 j 段是 [l, r]（闭区间），那么：

• • 该段的 nums 元素和 = P[r+1] - P[l]
• • 该段的 cost 元素和 = S[r+1] - S[l]
• • 该段的权重 = P[r+1] + k * j

但是注意题目描述中“nums 从开头到 r 的前缀和”就是 P[r+1]（如果前缀和定义为包含 r 位置元素）。

实际上，代码中似乎直接用了“到 r 的累加和”作为权重的一部分，并且 k*j 是额外加的。

3. 动态规划思路

定义 dp[i] 为将 nums[0..i-1] 分割成若干段的最小总代价（i 个元素，索引 0 到 i-1）。

转移：

dp[0] = 0
dp[i] = min_{0 <= j < i} { dp[j] + (P[i] + k * (段编号)) * (S[i] - S[j]) }

但这里有个问题：段编号依赖于前面已经分了多少段。如果 [j..i-1] 是最后一段，那么它的编号 = 前面 j 个元素被分成的段数 + 1。

如果我们令最后一段是第 t 段，那么 t 并不是直接由 j 决定的，而是由 j 对应的分割方式决定的段数。这样直接做是二维 DP（dp[i][t] 表示前 i 个元素分成 t 段的最小代价），但 t 最大为 n，复杂度 O(n³) 可能太高（n≤1000 时不行）。

4. 代码中的优化方法（凸包技巧）

代码里用的是斜率优化（convex hull trick）来避免枚举所有 j，将 O(n²) 优化到 O(n)。

观察：

• • 如果我们设最后一段是 [j, i-1]，那么：
  • • 这一段的 cost 和 = sc[i] - sc[j]（sc 是 cost 前缀和）
  • • 这一段的 nums 前缀和到 i-1 位置 = sn[i]（sn 是 nums 前缀和）
  • • 段编号 = 前面有若干段，假设前 j 个元素已经分成若干段，段数未知，但我们可以把 k * 段编号 写成 k * (m+1)，其中 m 是前 j 个元素的段数。

实际上，在 DP 中，如果我们把 k * 段编号 拆开，会发现对于最后一段，它的 k * 段编号 = k * (前 j 个元素的段数 + 1)。

但前 j 个元素的段数在 dp[j] 中已经隐含了，我们需要把 k * 段编号 分离出来重新组合。

技巧：将 k * (段编号) 乘到 cost 和上，并重新整理项，可以变成：

总代价 = sum_{各段} (P[r] + k*段编号) * cost_sum(段)
= sum_{各段} P[r] * cost_sum(段) + k * sum_{各段} (段编号 * cost_sum(段))

第二项中，段编号 * cost_sum(段) 可以理解为：对于每个位置 i 的 cost[i]，它被乘的系数是它所在段的段编号。

所以总代价 = sum_i (P[i] * cost[i]) + k * sum_i (段编号_i * cost[i])，其中 段编号_i 是位置 i 所在的段编号。

这样问题变成：给每个位置分配一个段编号（编号从 1 开始递增，且编号必须随 i 增大不减），最小化 sum_i (段编号_i * cost[i])，再加上一个固定项 sum_i (P[i] * cost[i])。

固定项与分段无关，所以问题简化为最小化 sum_i (段编号_i * cost[i])。

这就是经典的分段线性代价问题，可以用凸包优化。

5. 代码流程解析

代码中：

• • totalCost = 总 cost 和。
• • q 是维护的下凸包（存的点是 (x, y) 形式）。
• • 循环 i 从 0 到 n-1：
  1. 1. 更新 sumNum（nums 前缀和）和 sumCost（cost 前缀和）。
  2. 2. 构建查询直线 p = (-sumNum - k, 1)，在凸包上找最小值点（斜率优化标准步骤）。
  3. 3. 用找到的最小值更新当前状态，并构建新的直线 p = (sumCost, ...) 加入凸包，维护凸包性质。

这个做法本质是：

• • 把 DP 转移 dp[i] = min_j { dp[j] + (P[i] + k*(t)) * (S[i]-S[j]) } 通过代数变形，转化成斜率优化形式。
• • 用单调队列维护下凸包，每次在队首删除不优的，队尾删除破坏凸性的。

6. 时间复杂度与空间复杂度

• • 时间复杂度：O(n)
  • • 循环 i 从 0 到 n-1，每个元素进出队列最多一次（均摊 O(1)），所以总 O(n)。
• • 空间复杂度：O(n)
  • • 队列 q 最多存储 n 个点。
  • • 其他变量 O(1)。

7. 总结步骤

1. 1. 问题转化：将总代价公式拆成固定项和与分段相关的项，发现最小化 sum(段编号_i * cost[i]) 是核心。
2. 2. DP 设计：设 dp[i] 为前 i 个元素的最小代价，转移时枚举最后一段起点 j。
3. 3. 斜率优化：将转移方程整理成直线形式 dp[i] = min_j { A(j) + B(j) * C(i) }，利用凸包快速找最小值。
4. 4. 凸包维护：用单调队列维护候选直线，保证每次查询 O(1) 均摊。
5. 5. 结果提取：最终答案是 dp[n] 加上固定项。

最终答案：

• • 时间复杂度：O(n)
• • 空间复杂度：O(n)

Go完整代码如下：

.

package main

import (
    "fmt"
)

type vec struct{ x, y int }

func (a vec) sub(b vec) vec { return vec{a.x - b.x, a.y - b.y} }
func (a vec) det(b vec) int { return a.x*b.y - a.y*b.x }
func (a vec) dot(b vec) int { return a.x*b.x + a.y*b.y }

func minimumCost(nums, cost []int, k int)int64 {
    totalCost := 0
    for _, c := range cost {
        totalCost += c
    }

    q := []vec{{}}
    sumNum, sumCost := 0, 0
    for i, x := range nums {
        sumNum += x
        sumCost += cost[i]

        p := vec{-sumNum - k, 1}
        forlen(q) > 1 && p.dot(q[0]) >= p.dot(q[1]) {
            q = q[1:]
        }

        // 一边算 DP 一边构建下凸包
        p = vec{sumCost, p.dot(q[0]) + sumNum*sumCost + k*totalCost}
        forlen(q) > 1 && q[len(q)-1].sub(q[len(q)-2]).det(p.sub(q[len(q)-1])) <= 0 {
            q = q[:len(q)-1]
        }
        q = append(q, p)
    }
    returnint64(q[len(q)-1].y)
}

func main() {
    nums := []int{4, 8, 5, 1, 14, 2, 2, 12, 1}
    cost := []int{7, 2, 8, 4, 2, 2, 1, 1, 2}
    k := 7
    result := minimumCost(nums, cost, k)
    fmt.Println(result)
}

Python完整代码如下：

.

# -*-coding:utf-8-*-

from collections import deque

class Vec:
    def __init__(self, x: int, y: int):
        self.x = x
        self.y = y

    def sub(self, b: "Vec") -> "Vec":
        return Vec(self.x - b.x, self.y - b.y)

    def det(self, b: "Vec") -> int:
        return self.x * b.y - self.y * b.x

    def dot(self, b: "Vec") -> int:
        return self.x * b.x + self.y * b.y

def minimum_cost(nums, cost, k):
    total_cost = sum(cost)

    q = deque([Vec(0, 0)])
    sum_num = 0
    sum_cost = 0
    for i, x in enumerate(nums):
        sum_num += x
        sum_cost += cost[i]

        # 用于在队首进行二分/查找的向量
        search = Vec(-sum_num - k, 1)
        while len(q) > 1 and search.dot(q[0]) >= search.dot(q[1]):
            q.popleft()

        # 计算当前状态的向量，并维护下凸包（单调保持）
        newv = Vec(sum_cost, search.dot(q[0]) + sum_num * sum_cost + k * total_cost)
        while len(q) > 1 and q[-1].sub(q[-2]).det(newv.sub(q[-1])) <= 0:
            q.pop()
        q.append(newv)

    returnint(q[-1].y)

if __name__ == "__main__":
    nums = [4, 8, 5, 1, 14, 2, 2, 12, 1]
    cost = [7, 2, 8, 4, 2, 2, 1, 1, 2]
    k = 7
    result = minimum_cost(nums, cost, k)
    print(result)

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展