DeepSeek LeetCode 3826. 最小分割分数 Java实现

针对 LeetCode 3826“最小分割分数”这里提供两种主流的 Java 解法分治 DP 优化 和 斜率优化 (CHT)。 题目回顾· 目标将数组 nums 分割成恰好 k 个连续非空子数组。· 子数组值sum * (sum 1) / 2 (sum 是该子数组元素和)。· 目标最小化所有子数组“值”的总和。---⚙️ 解法一分治 DP 优化 (Divide and Conquer DP)这种方法利用了最优决策点的单调性将时间复杂度优化到 O(k * n * log n)更易理解且不易出错。javaclass Solution {// 计算子数组 [l, r) 的值private long score(int l, int r, long[] pref) {long s pref[r] - pref[l];return s * (s 1) / 2;}// 分治计算DPprivate void compute(int L, int R, int optL, int optR, long[] pref, long[] prev, long[] cur) {if (L R) return;int mid (L R) 1;long bestVal Long.MAX_VALUE;int bestJ -1;int hi Math.min(optR, mid - 1);for (int j optL; j hi; j) {if (prev[j] Long.MAX_VALUE) continue;long cand prev[j] score(j, mid, pref);if (cand bestVal) {bestVal cand;bestJ j;}}cur[mid] bestVal;if (bestJ -1) return;compute(L, mid - 1, optL, bestJ, pref, prev, cur);compute(mid 1, R, bestJ, optR, pref, prev, cur);}public long minPartitionScore(int[] nums, int k) {int n nums.length;long[] pref new long[n 1];for (int i 1; i n; i) {pref[i] pref[i - 1] nums[i - 1];}long[] prev new long[n 1];long[] cur new long[n 1];Arrays.fill(prev, Long.MAX_VALUE);Arrays.fill(cur, Long.MAX_VALUE);prev[0] 0;// 初始化分成1段的情况for (int i 1; i n; i) {prev[i] score(0, i, pref);}// 迭代分段数for (int g 2; g k; g) {Arrays.fill(cur, Long.MAX_VALUE);// 计算当前层所有状态compute(g, n, g - 1, n - 1, pref, prev, cur);// 交换数组滚动更新long[] tmp prev;prev cur;cur tmp;}return prev[n];}}· 时间复杂度: O(k * n * log n)· 空间复杂度: O(n)---⚙️ 解法二斜率优化 (Convex Hull Trick) AC这是官方解法利用凸包将时间复杂度进一步降至 O(k * n)。代码稍复杂但效率最高。javaimport java.util.*;class Solution {// 使用长整型避免溢出private long[][] hull; // 存储凸包上的直线 (斜率m, 截距c)private int head, tail;// 计算两条直线的交点判断是否需要移除中间直线private boolean bad(long m1, long c1, long m2, long c2, long m3, long c3) {// 检查 (c3 - c1) * (m1 - m2) (c2 - c1) * (m1 - m3)return (c3 - c1) * (m1 - m2) (c2 - c1) * (m1 - m3);}// 添加直线 y m*x cprivate void addLine(long m, long c) {while (tail - head 2 bad(hull[tail-2][0], hull[tail-2][1],hull[tail-1][0], hull[tail-1][1],m, c)) {tail--;}hull[tail][0] m;hull[tail][1] c;tail;}// 在 x 处查询最小值private long query(long x) {while (tail - head 2 hull[head][0] * x hull[head][1] hull[head1][0] * x hull[head1][1]) {head;}return hull[head][0] * x hull[head][1];}public long minPartitionScore(int[] nums, int k) {int n nums.length;long[] pref new long[n 1];for (int i 0; i n; i) {pref[i1] pref[i] nums[i];}// dp_prev[i]: 前 i 个元素分成上一段数的最小两倍分数long[] dp_prev new long[n 1];for (int i 1; i n; i) {long s pref[i];dp_prev[i] s * (s 1);}hull new long[n 1][2];for (int seg 2; seg k; seg) {long[] dp_cur new long[n 1];head 0;tail 0;for (int i 1; i n; i) {int j i - 1;if (j 1) {long m -2 * pref[j];long c dp_prev[j] pref[j] * pref[j] - pref[j];addLine(m, c);}if (tail head) {long best query(pref[i]);dp_cur[i] best pref[i] * pref[i] pref[i];} else {dp_cur[i] Long.MAX_VALUE / 2;}}dp_prev dp_cur;}return dp_prev[n] / 2;}}· 时间复杂度: O(k * n)· 空间复杂度: O(n)核心思路说明1. 避免浮点数计算时统一使用两倍分数 (*2)最后再除以2。2. 转移方程变形将原DP转移方程展开变形为求直线 y m*x c 在 x pref[i] 处的最小值。3. 维护下凸包每个可能的切分点 j 都是一条直线。随着 i 增加用单调队列维护一个下凸包快速剔除不可能成为最优解的直线。选择哪种实现取决于你的偏好分治DP更直观且不易出错斜率优化则在理论上效率更高。