第三节 下降/非降子序列问题
这种题目在ACM竞赛中，通常作为“水题”出现。但是水题不水，不了解动态规划的还是AC不了这种类型。我们将会在这一节中，学习解决这种类型题。
模型抽象
子序列问题分为下降子序列问题和非降子序列问题，解决方法类似：
- 最长非降子序列问题：在一个无序序列a[1],a[2],…,a[n]中，找到一个最长的子序列满足：
- a[i]<=a[j]<=…<=a[m]
- i<j<…<m
- 最长下降子序列问题：在一个无序序列a[1],a[2],…,a[n]中，找到一个最长的子序列满足：
- a[i]>a[j]>…>a[m]
- i>j>…>m
我们从动态规划的三要素入手，来分析这种问题是否能使用动态规划来解决：如果要找到一个长度为k的子序列，那么我们需要一个长度为k-1的满足条件的的序列，再判断第k个元素是否满足条件，这显然满足最优子结构。在考虑第i个元素时，只需要看前面的i-1个，满足无后效性。因此这类题目可以使用动态规划来解决。
下面我们来做一道经典的题目：hdu1257：最少拦截系统
1 |
