石子合并求最大代价——极端决策
根据题意，求解石子合并最大代价的动态转移方程为：
通过打表，我们猜测，决策点在两个端点，可以获得最优解。
结论
求最大代价 \(dp(i,j)\) 时可以采用极端决策（即决策点 \(k\) 只取区间两端，也就是 \(k=i\) 或 \(k=j-1\)，无需枚举所有中间点）。
核心原因是：最大代价的最优分割策略具有 “贪心倾向性”——让较大的子堆总重量被多次累加，而极端分割恰好能满足这一要求。
证明
明确一个结论
一个石子序列 \({a_i}\)，对于任意区间 \([i,j]\)
- 如果 \(a_i > sum(i+1,j)\)，我们在每次合并的时候，都包含 \(a_i\) 可以使答案最优，此时 \(dp(i,j)\) 决策点为 \(j-1\)。
- 如果 \(a_j > sum(i,j-1)\)，我们在每次合并的时候，都包含 \(a_j\) 可以使答案最优，此时 \(dp(i,j)\) 决策点为 \(i\)。
- 对于石子合并的代价数组，有 \(dp(i,i) = 0（1\le i\le n）\)
以下针对不满足上面两个结论进行讨论。
用数学归纳法证明
1.基础结论验证
设合并石子的区间宽度为 \(len\)
- 当 \(len=1\) 时，无需合并，默认成立
- 当 \(len=2\) 时，只有一种合并方式，符合极端决策，成立
- 当 \(len=3\) 时，有两种合并方式，均满足极端决策，成立
2. 归纳假设
假设对于任意区间宽度 \(len<m\) 成立，最优分割点为极端点，即:
3. 目标
对于区间 \(len = m\)，需要证明任意非极端分割点 \(k_0\in(i,j-1) 满足\)
两边同时减去 \(sum(i,j)\)
即需要证明：
3.1 用归纳假设展开所有dp值
- 区间 \([i,k_0]\)
最优分完点为极端点，取 \(k=i\)（取另外一个极端点证明方法类似），因此：
- 区间 \([k_0+1,j]\)
最优分完点为极端点，取 \(k=k_0+1\)（取另外一个极端点证明方法类似），因此：
- 区间 \([i+1,j]\)
由原始的动态转移方程，其代价是所有分割点的最大值加区间和：
因为 \(k_0\in(i,j-1)\)
所以 \(k_0\) 是 \((4)\) 的决策点的一个候选值，故：
3.2 计算非极端分割点的代价和
将 \((1)\) 和 \((2)\) 代入，计算非极端分割点的代价和：
3.3 关联极端分割点的代价和
极端分割点 \(k=i\) 代价和为（\(k=j-1\) 证明方法类似）：
现在我们将 \((5)\) 和 \((6)\) 建立关系：
对于区间 \([i+1,k_0]\cup [k_0+2,j]=[i+1,j]-\{k_0+1\}\)，显然有
已知 \(s(i,j) = s(i+1,j) + a_i\)，代入 \((5)\) 得：
3.4 最终对比
因为 \(a_i \ge 0\)，
所以
后面用反证法证明
结合 \((6)\) 和 \((9)\) 可得：
同理可证：
得证。
4 反证法证明式子 (9)
假设 \((9)\) 不成立，则有：
结合 \((4)\) 可得：
两边同时减去 \(dp(k_0+1,j)\)，得到：
结合 \((1)\) 式，可得：
两边消去 \(dp(i+1,k_0)\)，得到
现在比较两者的大小关系：
结合本文开头明确的结论，此时有 \(sum(k_0,j)\gt a_i\)
因此 \(sum(i+1,j)>sum(i,k_0)\)，与假设推导出的式子相矛盾
假设不成立。
从而证明，原式成立。