土法炼钢兴趣小组的算法知识备份

分治优化 DP：决策单调性的力量

2025-07-15 | algorithms | #dp #divide-and-conquer #quadrangle-inequality #knuth-optimization

当 DP 的最优决策点具有单调性时，分治技巧可以将 O(n^2) 优化到 O(n log n)。四边形不等式是识别这种结构的关键数学工具。