题目知识点
动态规划（DP）
题意说明
当 且 ， 值域不大时，这题其实是一个十分简单的 DP，就类似于数字三角形。直接记 为 「以 为终点，最长合法序列的长度」。则对于所有（已经存在的）整点，有：
但是我们可以发现，当 ， 值域比较大时就不行了，所以我们需要进行优化，可以考虑记 表示 「以 号点结尾的合法序列，最长能有多长」。则可以表示为：
不会存在环状结构（因为合法序列必须向右、上方发展），所以把刚刚的 DP 改造一下，就是本题的正解了：记 表示 「以 号点结尾，已经使用掉了 个自由点，获得的收益」。可以表示为：
实现细节
本题的求值顺序值得注意，合法路径可能形如 。
有两种解决方法：
- 记忆化搜索（记忆化搜索最擅长解决求值顺序混乱的DP）。
- 预先按 ， 排序，使得编号大的点一定是从编号小的点转移过来。