这道题（LeetCode 3826）是一道困难题，标准解法是斜率优化动态规划 (DP)。
📝 题目理解
· 任务：将数组 nums 分割成恰好 k 个连续非空子数组。
· 子数组的“值”：sum * (sum + 1) / 2，sum 是该子数组元素和。
· 目标：最小化所有子数组“值”的总和。
· 示例：nums = [5,1,2,1], k = 2，最优分割为 [5] 和 [1,2,1]。分数为 (5*6/2) + (4*5/2) = 15 + 10 = 25。
⚙️ 核心思路：斜率优化DP
直接动态规划的时间复杂度是 O(k * n^2)，对于 n <= 1000 的场景依然可能超时。斜率优化利用转移方程的特性，将时间复杂度降为 O(k * n)。
1. 定义状态：dp[j][i] 表示将前 i 个元素分成 j 段的最小“分数”的两倍（避免小数）。
2. 状态转移：枚举最后一段的开始位置 p，dp[j][i] 由 dp[j-1][p] 转移而来。
· 令 s[i] 为前缀和，转移方程核心部分是：
dp[j][i] = min( dp[j-1][p] + (s[i] - s[p]) * (s[i] - s[p] + 1) )
3. 斜率优化：
· 将上述方程展开，可转化为求一系列直线在特定 x 坐标上的最小值问题。
· 每个可能的 p 都对应一条直线 y = m*x + c，其中：
· 斜率 m = -2 * s[p]
· 截距 c = dp[j-1][p] + s[p]^2 - s[p]
· 查询点的 x = s[i]
· 通过维护一个下凸包（或上凸包）并利用单调队列，可以在 O(1) 时间内找到最优的 p。
💻 Python3 代码实现 (斜率优化)
```python
from collections import deque
from typing import List
class Solution:
def minPartitionScore(self, nums: List[int], k: int) -> int:
n = len(nums)
# 1. 计算前缀和
pref = [0] * (n + 1)
for i in range(n):
pref[i+1] = pref[i] + nums[i]
# 2. 初始化 dp_prev: 只分1段的情况
# dp_prev[i] 代表将前 i 个元素分成 1 段的分数的两倍
dp_prev = [0] * (n + 1)
for i in range(1, n + 1):
s = pref[i]
dp_prev[i] = s * (s + 1) # 两倍分数
# 3. 迭代分段数从 2 到 k
for _ in range(2, k + 1):
dp_cur = [0] * (n + 1)
q = deque()
# 从 j = step-1 开始，确保前面至少有 step-1 个元素
# 这里 j 对应转移方程中的 p (前一段的结束位置)
# 我们提前将候选的直线加入队列
for i in range(1, n + 1):
# 将新的候选直线 (j = i-1) 加入队列
j = i - 1
if j >= 1: # 确保前一段至少有1个元素，且前一段能分成 _-1 段
# 计算新直线的斜率 m 和截距 c
# 注意：这里使用 dp_prev[j]，它代表将前 j 个元素分成 _-1 段的最优值
m = -2 * pref[j]
c = dp_prev[j] + pref[j] * pref[j] - pref[j]
new_line = (m, c)
# 维护下凸包：从尾部移除无用的直线
while len(q) >= 2:
m1, c1 = q[-1]
m2, c2 = q[-2]
# 检查新直线是否让倒数第一条直线变得无用
# 条件: (c1 - c2) / (m2 - m1) >= (c - c1) / (m1 - m)
# 为避免浮点数，交叉相乘
if (c1 - c2) * (m1 - m) >= (c - c1) * (m2 - m1):
q.pop()
else:
break
q.append(new_line)
# 从队首移除在 x = pref[i] 处不是最优的直线
while len(q) >= 2:
m1, c1 = q[0]
m2, c2 = q[1]
# 如果直线1在直线2之上，则移除直线1
# 条件: m1*x + c1 >= m2*x + c2
if m1 * pref[i] + c1 >= m2 * pref[i] + c2:
q.popleft()
else:
break
# 计算 dp_cur[i]: 用队首的最优直线计算
if q:
best_m, best_c = q[0]
dp_cur[i] = best_m * pref[i] + best_c + pref[i] * pref[i] + pref[i]
else:
# 处理不可能的状态（如 i < 当前分段数），保持为0或inf
# 但根据循环逻辑，i >= 分段数时，队列必有元素
dp_cur[i] = float('inf')
dp_prev = dp_cur
# 最终答案要除以2（因为我们计算的是两倍分数）
return dp_prev[n] // 2
```
⏳ 复杂度分析
· 时间复杂度: O(k * n)，其中 n 是数组长度。
· 空间复杂度: O(n)，用于存储 DP 数组和单调队列。
希望这份详细的解析和代码实现能帮助你理解这道题！
