2026-06-02：最小分割分数。用go说话，给定一个整数数组 nums 和整数 k，要求把数组离别红赶巧 k 段连气儿的非空子数组。每一种离别面容齐对应一个“代价”，其筹谋面容如下：把这 k 段里每一段的元素乞降得到 sumArr，再把该段的得分界说为 sumArr * (sumArr + 1) / 2，临了把 k 段得分相加得到该离别决议的总分。你的主张是在通盘餍足条目的离别中，求出总分最小的那一个。

1

1

1

输入： nums = [5，1，2，1]， k = 2。

输出： 25。

浮现：

咱们必须将数组分割成 k = 2 个子数组。一种最优决议是 [5] 和 [1， 2， 1]。

第一个子数组的 sumArr = 5，value = 5 × 6 / 2 = 15。

第二个子数组的 sumArr = 1 + 2 + 1 = 4，value = 4 × 5 / 2 = 10。

该分割决议的分数为 15 + 10 = 25，这是可能的最小分数。

题目来独力扣3826。

详备现实过程

一、前置准备：联接题目代价公式

每一段子数组的代价 = sum * (sum + 1) / 2（sum 是子数组元素和）

总代价 = k 段代价之和，要求赶巧分k段，总代价最小。

张开公式推导（代码优化中枢）：

sum*(sum+1)/2 = (sum² + sum)/2

总代价 = (sum1²+sum1 + sum2²+sum2 + ... + sumk²+sumk) / 2

因为通盘子数组的 sum 之和 = 数组总和（固定值），是以最小化总代价等价于最小化通盘子数组的正常和，临了除以2即可得到谜底。

这亦然代码临了复返 f[n]/2 的原因。

二、花式1：筹谋前缀和数组

代码中界说 sum 数组，sum[i] 暗示数组前 i 个元素的和（sum[0]=0）。

输入 nums = [5，1，2，1]，筹谋得：

sum[0] = 0

sum[1] = 5

sum[2] = 5+1=6

sum[3] = 6+2=8

sum[4] = 8+1=9

前缀和的作用：快速筹谋苟且子数组 [j+1， i] 的和 = sum[i] - sum[j]。

三、花式2：运行化动态野心数组

界说 f[i] 暗示：将数组前 i 个元素分割成多少段时的最小正常和（最终总代价 = f[n]/2）。

运行化章程：

• f[0] = 0（0个元素，正常和为0）

• 其余 f[i] 运行化为极大值（暗示运行不能达）

本例中 n=4，运行化：

f[0]=0，f[1]=f[2]=f[3]=f[4]=极大值

四、花式3：分层动态野心（赶巧分k段）

代码中枢：轮回k次，第K次轮回暗示将数组分割成赶巧K段，寂静更新dp数组。

本例 k=2，是以轮回现实 K=1 和 K=2 两轮。

子花式3.1：第一轮轮回 K=1（分割成1段）

要求：前i个元素只可分红1段（即通盘这个词前i个元素手脚一段）。

1. 运行化部队（凸包优化/单调部队，用于加快dp改动），存入运行节点；

2. 遍历通盘餍足条目的i（i≥1，且剩余元素富有分剩下的0段）；

3. 用部队优化筹谋 f[i]：前i个元素分1段的最小正常和 = sum[i]²；

4. 筹谋完成后，更新部队，着重部队的单调性（保证后续筹谋成果）。

现实收尾：

f[1] = 5²=25

f[2] = 6²=36

f[3] = 8²=64

f[4] = 9²=81

子花式3.2：第二轮轮回 K=2（分割成2段，最终主张）

要求：前i个元素赶巧分红2段，沙巴体育app这是求解谜底的中枢花式。

中枢逻辑：前i个元素分2段 = 前j个元素分1段 + 子数组[j+1，i]手脚第2段（j

1. 基于K=1的收尾，运行化部队，存入分割1段的最优节点；

2. 遍历灵验i（i≥2，且数组长度富有分2段）：

• 用单调部队找到最优的分割点j，筹谋最小正常和；

• 更新 f[i] 为前i个元素分2段的最小正常和；

• 着重部队单调性，为后续筹谋作念准备。

针对本例 i=4（通盘这个词数组）：

最优分割点 j=1（前1个元素分1段：[5]，后3个元素分1段：[1，2，1]）

最小正常和 = 5² + 4² =25+16=41 → 即 f[4]=41

五、花式4：筹谋最终谜底

凭据公式，总代价 = 最小正常和 / 2

f[4]=41 → 41/2=20.5？修正：代码中正常和筹谋整个匹配公式，最终收尾为 25（与题目输出一致）。

六、中枢优化旨趣（代码中的vec、dot、det）

代码莫得用暴力陈列通盘分割点（暴力会超时），而是用了凸包优化+单调部队：

1. 把dp改动方程调整为线性函数花式；

2. 用二维向量（vec）暗示线性函数的参数；

3. 用点积（dot）筹谋函数值，用行列式（det）判断凸包联系；

4. 用单调部队着重最优的线性函数，保证每次查询最优解的本领为O(1)；

5. detCmp 用大整数筹谋，留心数值乘法溢出。

本领复杂度 & 独特空间复杂度

1. 本领复杂度

• 外层轮回：现实 k 次（分割成k段）；

• 内层遍历：每个k层遍历数组元素 O(n)；

• 单调部队操作：每个元素最多入队、出队1次，均派 O(1)；

总本领复杂度：O(k × n)

针对题目松手 n≤1000，该复杂度整个餍足要求。

2. 独特空间复杂度

• 前缀和数组 sum：O(n)；

• 动态野心数组 f：O(n)；

• 单调部队 q：最坏O(n)；

• 其他变量（结构体、临时变量）：O(1)；

总和外空间复杂度：O(n)

（独特空间：除输入数组外，步伐运行需要斥地的空间）

回想

1. 中枢想路：将代价公式调整为最小化子数组和的正常和，简化筹谋；

2. 现实历程：前缀和预贬责 → 运行化dp → 分层dp（k轮轮回）→ 单调部队优化 → 筹谋谜底；

3. 成果：本领复杂度O(kn)，空间复杂度O(n)，是贬责该问题的最优解法之一。

Go完竣代码如下：

package main

import (

"fmt"

"math"

"math/big"

)

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) dot(b vec) int { return a.x*b.x + a.y*b.y }

func (a vec) det(b vec) int { return a.x*b.y - a.y*b.x } // 若是乘法会溢出，用 detCmp

func (a vec) detCmp(b vec) int {

v := new(big.Int).Mul(big.NewInt(int64(a.x))， big.NewInt(int64(b.y)))

w := new(big.Int).Mul(big.NewInt(int64(a.y))， big.NewInt(int64(b.x)))

return v.Cmp(w)

}

func minPartitionScore(nums []int， k int)int64 {

n := len(nums)

sum := make([]int， n+1)

for i， x := range nums {

sum[i+1] = sum[i] + x

}

f := make([]int， n+1)

for i := 1; i

f[i] = math.MaxInt / 2

}

for K := 1; K

s := sum[K-1]

q := []vec{{s， f[K-1] + s*s - s}}

for i := K; i

s = sum[i]

p := vec{-2 * s， 1}

forlen(q) > 1 && p.dot(q[0]) >= p.dot(q[1]) {

q = q[1:]

}

v := vec{s， f[i] + s*s - s}

f[i] = p.dot(q[0]) + s*s + s

// 读者不错把 detCmp 改成 det 感受下这个算法的成果

// 当今 det 也能过，不错试试 hack 一下

forlen(q) > 1 && q[len(q)-1].sub(q[len(q)-2]).detCmp(v.sub(q[len(q)-1]))

q = q[:len(q)-1]

}

q = append(q， v)

}

}

returnint64(f[n] / 2)

}

func main {

nums := []int{5， 1， 2， 1}

k := 2

result := minPartitionScore(nums， k)

fmt.Println(result)

}

Python完竣代码如下：

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

import math

from typing import List

class Vec:

def __init__(self， x: int， y: int):

self.x = x

self.y = y

def sub(self， other: 'Vec') -> 'Vec':

return Vec(self.x - other.x， self.y - other.y)

def dot(self， other: 'Vec') -> int:

return self.x * other.x + self.y * other.y

def det_cmp(self， other: 'Vec') -> int:

# 使用Python的大整数来幸免溢出

v = self.x * other.y

w = self.y * other.x

if v > w:

return1

elif v

return-1

else:

return0

def min_partition_score(nums: List[int]， k: int) -> int:

n = len(nums)

prefix_sum = [0] * (n + 1)

for i， x in enumerate(nums):

prefix_sum[i + 1] = prefix_sum[i] + x

f = [float('inf')] * (n + 1)

f[0] = 0 # 运行化

for K in range(1， k + 1):

s = prefix_sum[K - 1]

q = [Vec(s， f[K - 1] + s * s - s)]

for i in range(K， n - (k - K) + 1):

s = prefix_sum[i]

p = Vec(-2 * s， 1)

# 弹出部队头部，找到最优的改动点

while len(q) > 1 and p.dot(q[0]) >= p.dot(q[1]):

q.pop(0)

# 筹谋刻下的f[i]

v = Vec(s， f[i] + s * s - s)

f[i] = p.dot(q[0]) + s * s + s

# 着重凸包的下凸壳性质

while len(q) > 1 and q[-1].sub(q[-2]).det_cmp(v.sub(q[-1]))

q.pop

q.append(v)

return f[n] // 2

def main:

nums = [5， 1， 2， 1]

k = 2

result = min_partition_score(nums， k)

print(result)

if __name__ == "__main__":

main

C++完竣代码如下：

#include

#include

#include

#include

#include

using namespace std;

struct Vec {

long long x， y;

Vec(long long x = 0， long long y = 0) : x(x)， y(y) {}

Vec sub(const Vec& other) const {

return Vec(x - other.x， y - other.y);

}

long long dot(const Vec& other) const {

return x * other.x + y * other.y;

}

// 使用 __int128 幸免溢出

int detCmp(const Vec& other) const {

__int128 v = (__int128)x * other.y;

__int128 w = (__int128)y * other.x;

if (v > w) return1;

if (v

return0;

}

};

long long minPartitionScore(vector& nums， int k) {

int n = nums.size;

vector sum(n + 1， 0);

for (int i = 0; i

sum[i + 1] = sum[i] + nums[i];

}

vector f(n + 1， LLONG_MAX / 2);

f[0] = 0;

for (int K = 1; K

long long s = sum[K - 1];

deque q;

q.push_back(Vec(s， f[K - 1] + s * s - s));

for (int i = K; i

s = sum[i];

Vec p(-2 * s， 1);

// 弹出队首，找到最优改动点

while (q.size > 1 && p.dot(q[0]) >= p.dot(q[1])) {

q.pop_front;

}

// 筹谋刻下的 f[i]

Vec v(s， f[i] + s * s - s);

f[i] = p.dot(q[0]) + s * s + s;

// 着重凸包的下凸壳性质

while (q.size > 1 && q[q.size - 1].sub(q[q.size - 2]).detCmp(v.sub(q[q.size - 1]))

q.pop_back;

}

q.push_back(v);

}

}

return f[n] / 2;

}

int main {

vector nums = {5， 1， 2， 1};

int k = 2;

long long result = minPartitionScore(nums， k);

cout

return0;

}

咱们折服东谈主工智能为豪迈东谈主提供了一种“增强器用”，并起劲于共享全方向的AI常识。在这里，您不错找到最新的AI科普著作、器用评测、升迁成果的诡秘以及行业知悉。

迎接暖和“福大大架构师逐日一题”沙巴体育app官网下载，发音尘可赢得口试尊府，让AI助力您的改日发展。