洛谷 P1434 题记：线性动态规划
这道题目有两种解法：记忆化搜索和线性动态规划。实际上，两者都属于动态规划的范畴之内，而记忆化搜索因为具有更为直接的思路，因而更容易想到（虽然不一定了解这个术语）。记忆化搜索的原理是利用搜索子问题的重复性，本质就是使用额外的空间存储已经进行过的搜索结果，是一种以空间换时间的思路，在此不做赘述。
本篇题记主要描述在本题中，将二维平面搜索转换为线性动态规划的一些理解。
第一步：分析问题结构
将问题动态规划化需要三个条件：最优子结构、无后效性和子问题重复。其中最优子结构的“问题最优解基于子问题的最优解”结论，从理论上允许我们通过求解子问题的最优解，从而推断出原问题的最优解；无后效性则确保了子问题一定是可解、易解的，从理论上杜绝了循环依赖的问题；子问题重复则是对于效率上的一种保证。前两个条件确保了动态规划的可行性，第三个则确保了动态规划的有效性。
但是在本题中，数据是按照二维坐标排列的。这样就会产生两个问题：
- 索引有两个维度，排序复杂；
- 现有的索引并不利于子问题的划分（即坐标与“高度”之间无关联性）。
于是注意到题目中，“斜坡”是按照点的高度进行定义的，所以考虑将点按照高度进行排序，这样恰好满足了最优子问题的结构：当考虑“斜坡”是以在现有“斜坡”的基础上追加新的、长度为1的小“斜坡”的话，恰好形成了一系列以高度为顺序的子问题序列。也就是说，这个时候，只需要按照高度顺序进行某种最长升序子序列的状态转移方程进行求解即可。
第二步：明确状态转移方程
状态转移方程可以视作一类递归函数，不过实现的时候用的是数组，而这也正是对子问题重复特性的利用。实际上，状态转移方程就是动态规划算法的实现原型。完成目标参数值下的状态转移方程值求解，也就完成了对问题的求解。
这里的状态转移思路非常简单，以当前坐标为起点的最长路径是：所有可到达该点、且高度高于该点的坐标中，所具有的最长路径。
公式表述如下：
第三步：实现
基于上述思路，进行程序语言的书写就可以了。由于要设计高效算法，应该尽可能避免不必要的操作，在进行数据读入的时候就可以按照高度作为索引的数据结构进行保存。其余部分没有什么需要特别注意的，就是条件记得写对、不写漏就行。
