高级数据结构与算法设计 23：DP优化在什么条件下成立
22篇先证明状态与转移正确，再计算每个状态。优化动态规划时，这个顺序仍然重要：减少内存不能丢掉未来依赖，缩小候选集合不能排除真正最优决策。观察几行最优下标递增，只能形成猜测，不能授权程序跳过剩余候选。
本篇把一个非负数组切成固定数量的非空连续段，最小化各段元素和的平方之和。先建立朴素递推，再证明特定代价满足的四边形不等式，最后用决策单调性减少搜索。
状态包含用了多少段
输入n个非负整数a，以及段数g。输出最小代价和g个半开区间，它们按顺序无缝覆盖[0,n)，每段非空。n=0、g=0单独返回代价0与空方案；其余要求1≤g≤n。
令S_i为前i项之和，S_0=0，区间[k,i)代价W(k,i)=(S_i−S_k)²。沿用11篇前缀和的半开语义，一次区间和只需相减；不需要再建一个区间求和数据结构。
D_t[i]表示前i项恰分成t段的最小代价。D_0[0]=0，其余零段状态不可行；对i≥t：
最后一段必须是某个非空[k,i)，此前恰有t−1段。因此任意合法划分都被枚举；反过来，合法前缀方案接上最后一段仍合法。与22篇相同，上界与可达性两方向一起证明递推，而不是只说明“看起来可以转移”。
朴素每行O(n²)候选，g行O(gn²)。前缀和令每个候选O(1)，这里的整数算术先按单位成本计算；Python大整数求和、平方与比较仍有位长成本。
非负性怎样给出四边形不等式
取a≤b≤c≤d四个切点，为避免与输入数组名混淆，令相邻三段的和分别为x、y、z。非负输入保证x,z≥0。展开平方得
所以W(a,c)+W(b,d)≤W(a,d)+W(b,c)。这项Monge型不等式说明交叉端点的两种组合之间有确定的成本关系。若段和含负数，2xz可能为负，结论不再普遍成立。
对同一DP行，候选代价还加上D_(t−1)[k]。比较两个候选k时，这些只依赖k的项在四边形差式中抵消，因此不破坏相应不等式。不可行状态和k<i的三角形定义域仍要保留，不能给所有矩阵位置随意填0。
最左最优决策为何不会向左退
令opt(i)为状态D_t[i]取到最小值的最小k。假设i<j却有opt(j)=a<opt(i)=b。由于b<i，a和b对这两个状态都合法。
Monge不等式给出A(a,i)+A(b,j)≤A(a,j)+A(b,i)，其中A(k,i)=D_(t−1)[k]+W(k,i)。而b对i最优、a对j最优，给出反方向的两项不等式。合在一起只能全部相等，于是a也是i的最优决策，且a<b，与选择最左最优相矛盾。
因此opt(i)≤opt(j)。平局规则是证明的一部分：代码扫描候选递增，只有严格改善才替换，不在相等时换到不一致的另一端。
分治计算一整行
已知目标下标区间[l,r]的最优决策位于[lo,hi]，先计算中点mid，扫描合法候选lo到min(hi,mid−1)，得到best。单调性限制左半的决策不大于best，右半的决策不小于best，于是递归计算两半。
第一轮区间是[t,n]，候选范围[t−1,n−1]，没有预先排除任何合法候选。每次限制都来自已证明的单调性，所以计算出的值与朴素递推相同。
一层递归的候选区间基本被切分，边界best可被相邻子问题重复访问；总长度仍为O(n)，递归深度O(log(n+1))。每行O(n log(n+1))，g行O(gn log(n+1))。不把更强矩阵搜索算法的线性行成本标到这个分治实现上。
这些是满足非负性前提后的确定性最坏界，不是随机测试上的平均界。候选评估次数可用于核对程序工作，但没有包含解释器递归、数组访问及大整数运算的全部耗时。
一个会破坏优化的负数例子
取数组[1,1,2,−3]，计算恰好两段的一行。对前2、3、4项，最优切点分别是1、2、1，发生向左回退。
前3项在k=1、2时成本分别为10、8；前4项在k=1、2、3时成本分别为1、5、25，最优点唯一。若先算中点i=3得到best=2，再把i=4的候选限制为k≥2，就会输出5而非正确值1。
朴素递推对负数仍正确，失败的是减少候选的证明前提。教学接口因此允许基准版本处理负数，而优化版本显式拒绝负元素；不能让调用者从同一个函数名猜测隐藏限制。
值压缩与方案恢复分开计费
第t行只读取第t−1行，所以计算数值只需prev、current两个长度n+1的数组。完成整行后再交换，不能在计算中覆盖仍被其他状态读取的旧行。这把值表空间压到O(n)，并没有自动解决方案恢复。
教学实现为每个可行状态保存最优切点，父指针占O(gn)空间。恢复从(g,n)出发，把[k,i)加入答案，再变为(t−1,k)，经过g次选择得到完整划分。总空间仍为O(gn+n)，不是O(n)。
若不保存父指针而只保留两行，最优值仍可得到，但恢复时必须重算或采用另行证明的空间节省算法。不能先报两行的空间成本，再无成本地返回已经丢掉的整条决策路径。这里也不同于用位掩码编码子集状态：编码紧凑不会把2^n种不同子集自动变成多项式数量。
可复跑检查
实现位于examples/advanced-algorithms/partition_dp.py，partition_squared(values,groups,optimized=True)返回代价、半开区间列表和可行候选评估次数。不可行值用None表示，避免让0伪装成可行方案；关闭优化后允许负数。仓库根目录运行：
1 | |
独立参照枚举所有切点组合，直接对每段求和平方，不调用DP转移。实际枚举1093个长度0到6、元素0到2的数组，共6016个分组实例，两版本均与参照一致；另有100个固定种子随机实例与5个拒绝检查。恢复区间还独立检查非空、连续、全覆盖和代价一致。
负数反例的正确值1、错误限制后的值5和决策序列[1,2,1]均已实际核对。种子20260920的代表输入n=128、g=8，两个版本都返回42219；朴素版评估54392个可行候选，优化版5880个。计数不含跳过的None候选，也不是运行耗时或普遍加速倍数。真实stdout保存在examples/advanced-algorithms/results/partition_dp.json。
有限枚举检查实现是否偏离递推，一般优化正确性依赖前面的Monge与最左决策证明。随机输入通过率不替代条件证明；负数版本的拒绝也是接口承诺的一部分。
练习
- 完整展开四边形差式，指出非负假设实际用于哪两个相邻段和。能否给出含负元素、但某个特定四元组仍满足不等式的例子？为什么这还不足以证明全表单调？
- 不保存父指针，只保留最终最优值和输入。给出通过重跑前若干行逐步恢复切点的正确方法，并分析它相对于保存父指针增加的时间。
参考资料
- MIT 6.046：Problem Set 1 Solutions，Handout 8，PDF第5–6页，Monge矩阵的最左最小值单调性与分治搜索。本文针对三角形可行域另给合法性证明，使用逐行中点递归，不照搬更强算法的复杂度。
