第三节 下降/非降子序列问题

  这种题目在ACM竞赛中,通常作为“水题”出现。但是水题不水,不了解动态规划的还是AC不了这种类型。我们将会在这一节中,学习解决这种类型题。

模型抽象

  子序列问题分为下降子序列问题和非降子序列问题,解决方法类似:

  • 最长非降子序列问题:在一个无序序列a[1],a[2],…,a[n]中,找到一个最长的子序列满足:
  1.  a[i]<=a[j]<=…<=a[m]
  2.  i<j<…<m
  • 最长下降子序列问题:在一个无序序列a[1],a[2],…,a[n]中,找到一个最长的子序列满足:
  1. a[i]>a[j]>…>a[m]
  2. i>j>…>m

  我们从动态规划的三要素入手,来分析这种问题是否能使用动态规划来解决:如果要找到一个长度为k的子序列,那么我们需要一个长度为k-1的满足条件的的序列,再判断第k个元素是否满足条件,这显然满足最优子结构。在考虑第i个元素时,只需要看前面的i-1个,满足无后效性。因此这类题目可以使用动态规划来解决。

  下面我们来做一道经典的题目:hdu1257:最少拦截系统

  

1
2