Hard
题目描述
给定一个整数数组 nums 和一个整数 k。
你的任务是将 nums 精确地分割成 k 个子数组，并返回一个整数，表示所有有效分割中的最小可能得分。
分割的得分是其所有子数组值的总和。
子数组的值定义为 sumArr * (sumArr + 1) / 2，其中 sumArr 是其元素的总和。
示例 1：
输入：nums = [5,1,2,1], k = 2
输出：25
解释：
我们必须将数组分割成 k = 2 个子数组。一个最优分割是 [5] 和 [1, 2, 1]。
第一个子数组的 sumArr = 5，值 = 5 × 6 / 2 = 15。
第二个子数组的 sumArr = 1 + 2 + 1 = 4，值 = 4 × 5 / 2 = 10。
此分割的得分是 15 + 10 = 25，这是最小可能得分。
示例 2：
输入：nums = [1,2,3,4], k = 1
输出：55
解释：
由于我们必须将数组分割成 k = 1 个子数组，所有元素都属于同一个子数组：[1, 2, 3, 4]。
此子数组的 sumArr = 1 + 2 + 3 + 4 = 10，值 = 10 × 11 / 2 = 55。
此分割的得分是 55，这是最小可能得分。
示例 3：
输入：nums = [1,1,1], k = 3
输出：3
解释：
我们必须将数组分割成 k = 3 个子数组。唯一有效的分割是 [1], [1], [1]。
每个子数组的 sumArr = 1，值 = 1 × 2 / 2 = 1。
此分割的得分是 1 + 1 + 1 = 3，这是最小可能得分。
约束条件：
1 <= nums.length <= 10001 <= nums[i] <= 10^41 <= k <= nums.length
解题思路
这是一道经典的分割优化问题。我们需要将数组分成恰好 k 个子数组，使得总代价最小。
基本动态规划思路：
设 dp[i][j] 表示将前 j 个元素分成 i 个子数组的最小代价。状态转移方程为：
dp[i][j] = min(dp[i-1][t] + cost(t+1, j)) for all valid t
其中 cost(l, r) 表示子数组 nums[l...r] 的代价，即 sum * (sum + 1) / 2。
朴素的 DP 时间复杂度为 O(k*n²)，对于本题的数据范围可能会超时。
分治优化（Divide and Conquer Optimization）：
由于代价函数 sum * (sum + 1) / 2 是凸函数，满足四边形不等式，我们可以使用分治优化将复杂度降低到 O(knlog n)。
分治优化的核心思想是：对于状态 dp[i][j]，如果我们知道最优分割点在某个区间 [optL, optR] 内，那么可以通过分治的方式缩小搜索范围。
实现细节：
- 预处理前缀和数组，快速计算子数组和
- 使用分治函数递归求解最优分割点
- 在分治过程中，利用最优分割点的单调性进行剪枝
这种优化特别适用于分割类 DP 问题，当代价函数满足凸性质时能显著提升效率。
代码实现
class Solution {
public:
long long minPartitionScore(vector<int>& nums, int k) {
int n = nums.size();
vector<long long> prefix(n + 1, 0);
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
auto cost = [&](int l, int r) -> long long {
long long sum = prefix[r] - prefix[l];
return sum * (sum + 1) / 2;
};
vector<vector<long long>> dp(k + 1, vector<long long>(n + 1, 1e18));
dp[0][0] = 0;
function<void(int, int, int, int, int)> solve = [&](int level, int l, int r, int optL, int optR) {
if (l > r) return;
int mid = (l + r) / 2;
long long best = 1e18;
int bestK = -1;
for (int k = max(level - 1, optL); k <= min(mid - 1, optR); k++) {
long long val = dp[level - 1][k] + cost(k, mid);
if (val < best) {
best = val;
bestK = k;
}
}
dp[level][mid] = best;
if (l < r) {
solve(level, l, mid - 1, optL, bestK);
solve(level, mid + 1, r, bestK, optR);
}
};
for (int i = 1; i <= k; i++) {
solve(i, i, n, 0, n);
}
return dp[k][n];
}
};
class Solution:
def minPartitionScore(self, nums: List[int], k: int) -> int:
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
def cost(l, r):
s = prefix[r] - prefix[l]
return s * (s + 1) // 2
dp = [[float('inf')] * (n + 1) for _ in range(k + 1)]
dp[0][0] = 0
def solve(level, l, r, opt_l, opt_r):
if l > r:
return
mid = (l + r) // 2
best = float('inf')
best_k = -1
for k_val in range(max(level - 1, opt_l), min(mid, opt_r + 1)):
val = dp[level - 1][k_val] + cost(k_val, mid)
if val < best:
best = val
best_k = k_val
dp[level][mid] = best
if l < r:
solve(level, l, mid - 1, opt_l, best_k)
solve(level, mid + 1, r, best_k, opt_r)
for i in range(1, k + 1):
solve(i, i, n, 0, n)
return dp[k][n]
public class Solution {
public long MinPartitionScore(int[] nums, int k) {
int n = nums.Length;
long[] prefix = new long[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
long Cost(int l, int r) {
long sum = prefix[r] - prefix[l];
return sum * (sum + 1) / 2;
}
long[,] dp = new long[k + 1, n + 1];
for (int i = 0; i <= k; i++) {
for (int j = 0; j <= n; j++) {
dp[i, j] = long.MaxValue / 2;
}
}
dp[0, 0] = 0;
void Solve(int level, int l, int r, int optL, int optR) {
if (l > r) return;
int mid = (l + r) / 2;
long best = long.MaxValue / 2;
int bestK = -1;
for (int kVal = Math.Max(level - 1, optL); kVal <= Math.Min(mid - 1, optR); kVal++) {
long val = dp[level - 1, kVal] + Cost(kVal, mid);
if (val < best) {
best = val;
bestK = kVal;
}
}
dp[level, mid] = best;
if (l < r) {
Solve(level, l, mid - 1, optL, bestK);
Solve(level, mid + 1, r, bestK, optR);
}
}
for (int i = 1; i <= k; i++) {
Solve(i, i, n, 0, n);
}
return dp[k, n];
}
}
var minPartitionScore = function(nums, k) {
const n = nums.length;
const prefix = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
const cost = (l, r) => {
const sum = prefix[r] - prefix[l];
return sum * (sum + 1) / 2;
};
const dp = Array(k + 1).fill().map(() => Array(n + 1).fill(Infinity));
dp[0][0] = 0;
const solve = (level, l, r, optL, optR) => {
if (l > r) return;
const mid = Math.floor((l + r) / 2);
let best = Infinity;
let bestK = -1;
for (let kVal = Math.max(level - 1, optL); kVal <= Math.min(mid - 1, optR); kVal++) {
const val = dp[level - 1][kVal] + cost(kVal, mid);
if (val < best) {
best = val;
bestK = kVal;
}
}
dp[level][mid] = best;
if (l < r) {
solve(level, l, mid - 1, optL, bestK);
solve(level, mid + 1, r, bestK, optR);
}
};
for (let i = 1; i <= k; i++) {
solve(i, i, n, 0, n);
}
return dp[k][n];
};
复杂度分析
| 复杂度 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 分治优化DP | O(k × n × log n) | O(k × n) |
| 朴素DP | O(k × n²) | O(k × n) |
推荐解法： 分治优化DP，在满足数据约束的前提下具有更好的时间复杂度。