划分DP

划分型动态规划（划分DP）是一种处理特定类型问题的动态规划方法，常用于解决需要将数据结构（如数组、字符串等）划分成若干部分以优化某些目标函数的问题。这类动态规划问题的关键在于找到合适的状态表示和状态转移方程。下面是划分的$DP$一些常见做法：

主要分为两种类型：

$\color{red}\text{1、确定段数的划分}$

$\color{blue}\text{1.定义状态}$

首先定义动态规划的状态：

通常表示为$dp[i][j]$，其中$i$表示数据结构的某个终点（或起点），$j$可能表示划分的段数、划分的方式或其他根据问题需要定义的参数。

$\color{blue}\text{2. 状态转移方程}$

状态转移是动态规划的核心，需要找到从之前的状态到当前状态的转移方法。对于划分型DP，状态转移方程通常涉及枚举分割点或分割方式，从而将原问题分解为更小的子问题。形式上可能是这样的：

$ dp[i][j] = \min 或 \max \{dp[k][j-1] + cost(k, i)\}，其中 k < i。 $

这里$cost(k, i)$表示从$k$到$i$划分的代价，根据实际问题的需求，可以是求和、求最大值、求最小值等操作。

$\color{blue}\text{3. 初始化}$

合理的初始化是动态规划成功的关键。一般而言，$dp[0][0]$或$dp[i][0]$（根据问题定义而定）是比较容易确定的基础状态。有时候可能需要对$DP$数组进行特殊的初始化来适配边界条件。

$\color{blue}\text{4. 计算顺序}$

决定动态规划的计算顺序，是从小到大（自底向上）还是从大到小（自顶向下），以确保在计算当前状态时，所有需要的前置状态都已被计算。

$\color{blue}\text{5. 答案提取}$

根据问题的要求，最终的答案可能在中，也可能需要遍历$DP$表的某一行或某一列来找到答案，其中$n$和$m$分别代表数据结构的大小和问题中的其他参数。

$\color{blue}\text{示例应用场景}$

• 数组分割问题：给定一个数组，将其分割为$k$个连续的子数组，使得这$k$个子数组的最大和最小。
• 字符串编辑问题：给定一个字符串，通过分割成若干部分，并对每一部分进行编辑（如反转、替换）来达到某个目标。
• 任务调度问题：将$N$个任务分配给$K$个机器处理，每个任务只能分配给一个机器，如何分配以最小化总完成时间或最大化利润。

划分型DP的关键在于理解如何将大问题划分为小问题，并通过动态规划表来优雅地解决这些小问题。每种类型的问题都有其独特之处，因此在实践中需要根据问题的具体情况来调整DP的定义和转移方程。

$\color{red}\text{2、不确定段数的划分}$

$\color{blue}\text{1) 通用模板（枚举最后一段）}$

• 状态：$dp[i]$ 表示前 $i$ 个元素被划成若干段后的最优值（最小/最大看题意）。

• 转移（不可取空段）：

$$dp[i] = \operatorname{opt}\_{k<i}\Big\{\,dp[k] + \mathrm{segCost}(k+1, i)\,\Big\}\quad \text{(并满足段可行性，如长度/和值/最大最小差等约束)} $$

• 初始化：

  • 极小化：$dp[0]=0$，其余设为 $+\infty$；

  • 极大化：$dp[0]=0$，其余设为 $-\infty$。

• 方案恢复：用 pre[i]=argmin/argmax k 回溯即可。

关键点：把“合法段”的判定（长度区间、区间和上界、max-min 上界等）嵌入到候选 $k$ 的集合定义里，只在合法 $k$ 上取最优。

---

$\color{blue}\text{2) 常见目标类型与套路}$

$\color{purple}A.$ 最小化“各段代价之和”

• 形式：$\mathrm{segCost}(l,r)$ 给定，目标 $\min\sum \mathrm{segCost}$。

• 朴素：$O(n^2)$ 枚举 $k$。

• 优化 1（长度窗 + 区间最小）：若只允许段长 $L\le r-l+1 \le R$，

  $$dp[i]=\min_{k\in[i-R,\,i-L]} \{ dp[k] + \mathrm{segCost}(k+1,i) \} $$

  若 $\mathrm{segCost}$ 只依赖长度或能拆为 $A(i)+B(k)$，可用滑动窗口最小值 / 单调队列 / 线段树把区间最小做成 $O(\log n)$ 或摊还 $O(1)$。

• 优化 2（前缀和 O(1) 算段代价）：若 $\mathrm{segCost}$ 基于区间和/平方和等，预处理 prefix 即可 O(1) 求段代价，整体从 $O(n^2)$ 降到 $O(n^2)$ 的小常数版或配合其他优化进一步降复杂度。

• 优化 3（凸二次代价 → CHT/Li Chao）：若

  $$\mathrm{segCost}(k+1,i)=(S_i-S_k)^2 + C$$

  则

  $$dp[i]=S_i^2 + \min_k \{ dp[k]+C+S_k^2 - 2S_i S_k \} $$

  把 $k$ 看成直线 $y = m x + b$（$m=-2S_k$, $b=dp[k]+S_k^2+C$），在 $x=S_i$ 处查询最小值，用凸包优化（CHT）/ Li Chao Tree可做到均摊 $O(\log n)$。

$\color{purple}B.$ 最少段数（每段需“可行”）

• 目标：在每段满足约束（如区间和 $\le T$、max-min $\le D$）前提下，最少用多少段覆盖前 $i$。

• 形式：

  $$dp[i] = 1 + \min_{k \in \text{Feasible}(i)} dp[k]$$

• 两指针 + 维护可行窗口：若可行性关于区间扩张是单调的（如区间和随右端点右移而非降），可用双指针维护最左可行 $L_i$，则

  $$dp[i]=1+\min_{k\in[L_i-1,\,i-1]} dp[k]$$

  用队列/多重集/线段树维护区间最小即可 $O(n\log n)$ 甚至 $O(n)$。

$\color{purple}C.$ 段数-代价联合权衡（拉格朗日/Alien’s Trick）

• 想“段数不限，但尽量小且总代价也小”，可给每段加罚 $\lambda$：

  $$f_\lambda[i] = \min_{k<i}\{ f_\lambda[k] + \mathrm{segCost}(k+1,i) + \lambda \} $$

  同时维护使用段数 $cnt[i]=cnt[k]+1$ 的最优。

• 随 $\lambda$ 增大，最优段数单调不增。对 $\lambda$ 二分/三分/步进搜索，即可得到“恰好 $K$ 段”或“至多 $K$ 段”的最优值与方案（常用于把“未知段数”间接转成“控制段数”）。

$\color{purple}D.$ 最大化类（奖励可加）

• 同理，把 $\min$ 换成 $\max$，把不可行段视为 $-\infty$ 即可；优化思路一致。

---

$\color{blue}\text{3) 决策单调性与分治优化（可选）}$

若代价函数 $w(k,i)$ 满足四边形不等式/凸性等条件，且最优决策 $opt[i]$ 单调（$opt[i]\le opt[i+1]$），则

$$dp[i]=\min_{k<i}\{dp[k]+w(k,i)\}$$

可用分治优化将一层转移从 $O(n^2)$ 降到 $O(n\log n)$。
（是否满足条件需按题目 $w$ 的结构判定；常见于“长度相关 + 凸/凹”的场景。）

---

$\color{blue}\text{4) 实现细节易错点}$

• 严禁空段：转移只考虑 $k<i$。

• 不可行段：视为代价 $+\infty$（或在候选里直接排除）。

• 极值与溢出：平方和等用 64 位，必要时开更大整型。

• 方案恢复：pre[i] 记录取到最优的 $k$。

• 需要“段长下限/上限”时，把合法 $k$ 限定在窗口内。

---

$\color{blue}\text{5) 两个小例子（伪代码）}$

例 1：最少段数使得每段区间和 $\le T$

// 前缀和 S[i]；两指针维护最左可行 L
dp[0] = 0; for i=1..n: dp[i]=+INF
L = 1
for i in 1..n:
    while L<=i and S[i]-S[L-1] > T: L++
    // 需要 min dp[k] on k in [L-1, i-1]
    dp[i] = 1 + min_k dp[k]  (k ∈ [L-1, i-1])
    // 维护区间最小：用队列/线段树/可持久化 RMQ
答 = dp[n]

例 2：任意段数最小化 $\sum ( \text{段和} )^2 + C$（CHT 优化）

// S[i] 前缀和；把转化为直线集合查询
dp[0]=0
插入一条直线: y = m*x + b，其中 m = -2*S[0], b = dp[0] + S[0]^2 + C
for i in 1..n:
    x = S[i]
    best = 查询直线集合在 x 处的最小值   // Li Chao / CHT
    dp[i] = x*x + best
    // 由 k=i 产生的新直线
    m = -2*S[i]
    b = dp[i] + S[i]^2 + C
    向结构中插入直线 (m,b)
答 = dp[n]

---

$\color{blue}\text{6) 快速选型小抄}$

• 段长限制 + 段代价仅与长度/端点函数有关$\rightarrow$窗口 + 单调队列/线段树。

• 二次/凸型代价（依赖前缀和） $\rightarrow$ CHT / Li Chao。

• **只关心最少段数**且可行性单调 $\rightarrow$双指针 + 区间最小。

• 想“隐式控制段数”$\rightarrow$ 每段加罚 $\lambda$ 做参数搜（Alien’s trick）。

• 满足决策单调 $\longrightarrow$ 分治优化。