1D/1D动态规划优化初步所谓1D/1D动态规划，指的是状态数为O(n),每一个状态决策量为O(n)的动态规划方程。直接求解的时间复杂度为O(n2),但是，绝大多数这样的方程通过合理的组织与优化都是可以优化到O(nlogn)乃至O(n)的时间复杂度的。这里就想讲一讲我对一些比较初步的经典的优化方法的认识。本文中不想进行过多的证明与推导,主要想说明经典模型的建立、转化与求解方法。由于本人认识与水平相当有限,如果出现什么错误与疏漏,还请大牛多多指正。另外,也希望大牛们更多地向我们介绍一下有关动态规划优化的更深入的东西。本文中使用两种方式表示一个函数：f(x)与fx，用方括号表示的函数值可以在规划之前全部算出(常量),而用圆括号表示的函数值必须在规划过程中计算得到(变量)。无论是什么函数值一经确定，在以后的计算中就不会更改。经典模型一：f(x)=minf(i)+wi,xi=i相信这个方程大家一定是不陌生的。另外，肯定也知道一个关于决策单调性的性质：假如用k(x)表示状态x取到最优值时的决策，则决策单调性表述为：Vij,k(i)k(j)，当且仅当
