1D/1D动态规划优化初步

所谓 1D/1D 动态规划, 指的是状态数为 O(n), 每一个状态决策量为 O(n)的动态规划方程。直接求解的时间复杂度为 O(n2),但是,绝大多数这样的方程通过合理的组织与优化都是可以优化到 O(nlogn)乃至 O(n)的时间复杂度的。这里就想讲一讲我对一些比较初步的经典的优化方法的认识.