3500. 将数组分割为子数组的最小代价

发表于 2025-11-29 分类于力扣阅读次数： Waline：本文字数： 962 阅读时长 ≈ 3 分钟

考点

划分DP
后缀和
数学
前缀和

思路

题目里，每一段 $nums[l..r]$ 的代价是： \[ (\text{sumNums}(l,r) + k \cdot i)\cdot \text{sumCost}(l,r) \] 其中 $i$ 是这一段是第几个子数组。把它拆开： \[ (\text{sumNums}(l,r))\cdot \text{sumCost}(l,r) \;+\; k\cdot i\cdot \text{sumCost}(l,r) \]

第一部分 $ (l,r)(l,r)$ → 完全可以用前缀和算： $\text{sumNums}(l,r) = psNums[r] - psNums[l-1]$ $\text{sumCost}(l,r) = psCost[r] - psCost[l-1]$
麻烦在第二部分：$k\cdot i\cdot \text{sumCost}(l,r)$，这里有个「我是第几段」的 $i$。

你直觉会想：要知道 $i$，那不就得搞个 $dp[pos][i]$ 吗？ 然而这个 $k\cdot i$ 是可以整体重写的，最后只跟每段的左端点有关，跟 i 无关。

假设我们把数组分成三段：

第 1 段：$[l_1..r_1]$
第 2 段：$[l_2..r_2]$
第 3 段：$[l_3..r_3]$

只看那堆跟 $k$ 有关的项： \[ k\cdot 1\cdot \text{sumCost}(l_1,r_1) + k\cdot 2\cdot \text{sumCost}(l_2,r_2) + k\cdot 3\cdot \text{sumCost}(l_3,r_3) \] 把 $\text{sumCost}$ 展开成单点：

第 1 段的每个 cost 都被乘了 $1$
第 2 段的每个 cost 都被乘了 $2$
第 3 段的每个 cost 都被乘了 $3$

换个视角：对于某个位置 $p$，它属于哪一段？假设属于第 $t$ 段，那它的 cost 被乘上的就是 $k\cdot t$。

再从「后缀」看：从每一段的左端点往后看，一直到数组末尾的 cost 和：

从 $l_1$ 开始的后缀和：包含第 1、2、3 段全部元素，每个 cost 被统计了 3 次
从 $l_2$ 开始的后缀和：包含第 2、3 段，每个 cost 被统计了 2 次
从 $l_3$ 开始的后缀和：只包含第 3 段，每个 cost 被统计了 1 次

于是你会发现： \[ k\cdot \big(1\cdot \text{sumCost}(l_1,r_1) + 2\cdot \text{sumCost}(l_2,r_2) + 3\cdot \text{sumCost}(l_3,r_3)\big) \] 恰好等价于： \[ k\cdot \big( \underbrace{\text{sumCost}(l_1,n)}_{\text{从 }l_1\text{ 的后缀}} +\underbrace{\text{sumCost}(l_2,n)}_{\text{从 }l_2\text{ 的后缀}} +\underbrace{\text{sumCost}(l_3,n)}_{\text{从 }l_3\text{ 的后缀}} \big) \] 推广到一般情况可以严格证明（把求和按下标重排就行，博客里也有写到这一点哞靠靠+1）。

结论：

原来的那堆 $k\cdot i\cdot \text{sumCost}(l,r)$，在总和里，等价于：对每个子数组的左端点 $l$，加一项 \[ k \cdot \text{sumCost}(l,n) \] ——只跟左端点 l 有关，和「我是第几段 i」完全没关系了！

这一步一做完，你就完全不需要状态里存 j（段数）了。

预处理：

$psNums[i]$：前 i 个 nums 的和（psNums[0]=0，psNums[i+1]=psNums[i]+nums[i]）
$psCost[i]$：前 i 个 cost 的和（同理）

定义：

$dp[i]$：把区间 $[i..n-1]$ 划分成若干段的最小代价
边界：$dp[n]=0$

转移：枚举第一段的右端点 $j$（包含 i）：

这一段的 $\text{sumNums}(i,j) = psNums[j+1] - psNums[i]$
这一段的 $\text{sumCost}(i,j) = psCost[j+1] - psCost[i]$
「nums × cost」部分： $(psNums[j+1] - psNums[i]) \cdot (psCost[j+1] - psCost[i])$
那坨关于 $k$ 的部分，已经被我们改写为： 对「从 i 开始」的后缀 cost 的贡献： \[ k\cdot (\text{sumCost}(i,n-1)) = k\cdot (psCost[n]-psCost[i]) \] 注意：跟 j 无关，是固定常数！

于是转移式： \[ dp[i] = \min_{j \in [i,n-1]} \Big( (psNums[j+1] - psNums[i])\cdot (psCost[j+1]-psCost[i]) + k\cdot (psCost[n]-psCost[i]) + dp[j+1] \Big) \] 得到下面AC代码：

class Solution {
 public:
  long long minimumCost(vector<int>& nums, vector<int>& cost, int k) {
    // 前缀和
    long long preNums[1005], preCost[1005];
    memset(preNums, 0, sizeof(preNums));
    memset(preCost, 0, sizeof(preCost));
    int n = nums.size();
    for (int i = 1; i <= n; ++i) {
      preNums[i] = preNums[i - 1] + nums[i - 1];
      preCost[i] = preCost[i - 1] + cost[i - 1];
    }
    // DP
    long long f[1005];
    memset(f, 0x3f, sizeof(f));
    f[n + 1] = 0;
    for (int i = n; i >= 1; --i) {
      for (int j = i; j <= n; ++j) {
        long long x = preCost[j] - preCost[i - 1];
        long long y = preNums[j];
        long long z = preCost[n] - preCost[i - 1];
        f[i] = min(f[i], x * y + k * z + f[j + 1]);
      }
    }
    return f[1];
  }
};