这道题LeetCode 3826是一道困难题标准解法是斜率优化动态规划 (DP)。 题目理解· 任务将数组 nums 分割成恰好 k 个连续非空子数组。· 子数组的“值”sum * (sum 1) / 2sum 是该子数组元素和。· 目标最小化所有子数组“值”的总和。· 示例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. 状态转移枚举最后一段的开始位置 pdp[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 代码实现 (斜率优化)pythonfrom collections import dequefrom typing import Listclass Solution:def minPartitionScore(self, nums: List[int], k: int) - int:n len(nums)# 1. 计算前缀和pref [0] * (n 1)for i in range(n):pref[i1] 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 到 kfor _ 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 - 1if 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:breakq.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 c2if 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 数组和单调队列。希望这份详细的解析和代码实现能帮助你理解这道题 DeepSeek LeetCode 3826. 最小分割分数 Python3实现
这道题LeetCode 3826是一道困难题标准解法是斜率优化动态规划 (DP)。 题目理解· 任务将数组 nums 分割成恰好 k 个连续非空子数组。· 子数组的“值”sum * (sum 1) / 2sum 是该子数组元素和。· 目标最小化所有子数组“值”的总和。· 示例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. 状态转移枚举最后一段的开始位置 pdp[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 代码实现 (斜率优化)pythonfrom collections import dequefrom typing import Listclass Solution:def minPartitionScore(self, nums: List[int], k: int) - int:n len(nums)# 1. 计算前缀和pref [0] * (n 1)for i in range(n):pref[i1] 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 到 kfor _ 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 - 1if 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:breakq.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 c2if 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 数组和单调队列。希望这份详细的解析和代码实现能帮助你理解这道题