动态规划-最长不下降子序列（LIS）

时间：2020-03-22 21:54:38 阅读：54 评论：0 收藏：0 [点我收藏+]

最长不下降子序列（LIS）

最长不下降子序列（Longest Increasing Subsequence）是动态规划中的一个非常经典的问题：

在一个数字序列中，找到一个最长的子序列（可以不连续），使得这个子序列是不下降（非递减）的

例如 A = {1, 2, 3, -1, -2, 7, 9} ，它的最长不下降子序列是 {1, 2, 3, 7, 9}，长度为 5。

对于这个问题，最简单的办法就是暴力枚举每种情况，即对于每个元素有取和不取两种选择，然后判断这个序列是否为不下降序列。如果是不下降序列，就更新最大长度，但是很严峻的一个问题这个时候时间复杂度就变成了O（2ⁿ）了。

我们介绍一下动态规划的解法，时间复杂度为O（n²）：

首先设置一个数组 dp[] ，令 dp[i] 代表以 A[i] 结尾的最长递增子序列的长度，通过设置这个数组，最长递增子序列的长度就为 dp 中的最大值。

由于 dp[i] 是以 A[i] 作为结尾的最长不下降子序列的长度，因此只有两种情况：

A[i] 之前所有的元素都比 A[j] 大，那么 A[i] 只好自己形成一条 LIS，但是长度为 1，dp[i] = 1
A[i] 之前存在 A[j] <= A[i] ，此时只需要把 A[j] 添加到末尾就能形成一条新的 LIS，如果形成的 LIS 能够比当前以 A[i] 结尾的 LIS 长度更长，那么就把 A[i] 跟在以 A[j] 结尾的 LIS 后面，形成一条更长的 LIS，dp[i] = dp[j] + 1

综上，此时的状态方程的递推公式为

dp[i] = max(1, dp[j] + 1)

(j = 1, 2, ..., i -1 && A[j] <= A[i])

上面的状态方程隐含了边界：dp[i] = 1。显然 dp[i] 只与小于 i 的 j 有关，因此只要让 i 从小到大遍历即可求出整个 dp 数组。

此时，时间复杂度即为O（n²）。

代码实现如下：

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 100;
int A[N], dp[N], n;	// 序列和, dp数组, 数字总数

int main() {
  scanf("%d", &n);
  for(int i=1; i <= n; i++) {
    scanf("%d", &A[i]);
  }	// 从 1 ～ N 编号
  int ans = -1;	// 记录最大的 dp[i]
  for(int i = 1; i < n; i++) {
    dp[i] = 1;	// 至少能够自身成为一条 LIS
    for(int j = 1; j < i; j++){	// 只需要递归到小于 i
      // 如果不比之前的小，而且新形成的子序列更大，则接到这个人后面来
      if(A[i] >= A[j] && (dp[j] + 1 > dp[i])) {
        dp[i] = dp[j] + 1;
      }
    }
    ans = max(ans, dp[i]);	// 确定当前结束的最长子序列的长度之后，比较
  }
  printf("%d", ans);
  return 0;
}

希望对大家有帮助。# 最长不下降子序列（LIS）