【动态规划2】线性状态动态规划

对应进阶篇第 14 章。 我们在前一节初步介绍了动态规划。本节将会介绍动态规划中最常规的一类题型——线性状 态动态规划，以及其变种问题。 顾名思义，线性状态动态规划指的是一类状态定义与题设内容线性相关的动态规划。题设中 有序列（数组），那动态规划的状态就是一维的；如果题设中有棋盘（网格）、那么动态规划的 状态就是二维的……线性状态动态规划定义状态的时候经常会考虑“某类有序事件中前若干个子 事件的答案”。 一般来说，线性的状态最为直观，容易用有向无环图（DAG）表示，也比较容易理解。所以 遇到动态规划问题构造状态时，通常会最优先考虑能否采用线性状态。