线性DP

例题：POJ2279

思考：

考虑 dp_{i,j,k} 表示第 i 行，第 j 列，安排 k 去站的方案数。

错误原因：

安排 k 去站但是可能会造成重复选择 k 。

正解：

考虑 dp_{a1,a2,a3,a4,a5} 表示各排从左边起分别站了 a1,a2,a3,a4,a5 个人时，合影方案数。

疑惑：

Q1.为什么不用考虑某个位置究竟站的是谁？

Q2.怎样确定这个问题是无后效性的？

Q3.怎样确定这个问题具有最优子结构？

自我解答：

A1.题目要求每一列单调并且每一排单调，对于第一个位置，也就是最高的肯定站在第一个位置，但是对于第二高的就有两个选择 (如果在第二排可以站人的情况下) ，第二个人的站位也会影响之后的第三高的人的站位。其实在正解的 dp 状态设置上面，是有考虑到某个位置究竟站的是谁的，只是题目在于求方案数，而不是具体的方案情况。因此在实际的 dp 的含义上面是并没有考虑到某个位置究竟站的是谁，但在 dp 的状态转移过程中其实是有考虑到某个位置究竟站的是谁的。

A2.其实主要感觉和题目的本身有关系？因为在题目本身的操作中，其实隐藏的操作过程是选一个人站在某个位置上面对于这个操作仅有的操作来说，是无后效性的，因此这个问题无后效性。

A3.最优子结构说的是下一阶段的最优解能够由前面各个阶段的最优解求解，考虑到当前的站位方案数其实与下一站位方案数息息相关因此这个问题具有最优子结构。

小结：

感觉这个线性DP和我之前所做的线性DP都不同，首先是 dp 的状态都定义到了我没想到的五维，这看起来既暴力又美观（暴力美学）。

《算法竞赛进阶指南》： 设计动态规划的状态转移方程，不一定要以“如何计算出一个状态”的形式给出，你也可以考虑”一个已知状态应该更新哪些后续阶段的位置状态“。

收获： 1.对 无后效性 和 最优子结构 有了更深的认识。

2.对 DP状态的定义 的定义又多了一种认识。（以后要更大胆一点，之前一直觉得三维基本上都顶天难度了）

3.”状态“ ”阶段“ ”决策“ 动态规划的三要素。

4.”子问题重叠“ ”无后效性“ ”最优子结构“ 动态规划的三个基本条件。

自己之前对线性DP的一些求解流程：

1.读懂题。

2.根据题目的数据范围和求解对象定义DP的含义 即 dp_{i,j} 表示什么？

3.初始条件 和 答案确定。

4.写状态转移方程。

5.确定枚举顺序 和 限制条件。

6.写程序 AC。