DP专题 | LIS POJ - 2533

这篇来看LIS~上题。

POJ - 2533 Longest Ordered Subsequence

Description

A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1 <= i1 < i2 < ... < iK<= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).

一个数字序列ai是按照a1<a2<...<aN进行排列的上升序列，对于一个给定的数字序列(a1,a2,...,aN)，其子序列为(ai1,ai2,...,aiK)，其中1<=i1<i2<...<iK<=N。

例如对于序列(1, 7, 3, 5, 9, 4, 8) ，有多个子序列，如(1, 7), (3, 4, 8)，不过最长上升子序列是(1, 3, 5, 8).

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

给定一个数字序列，计算最长上升子序列的长度。

Input

The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000

第一行输入一个N，

第二行输入N个数。

Output

Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

输出最长子序列长度。

Sample Input

7
1 7 3 5 9 4 8

Sample Output

4

LIS是典型的DP题，dp[i]表示以数字a[i]结尾的最长子序列的最大长度，从位置1一直到N，显然可以采用递推的方式解决。

转移方程为dp[i] = max(dp[j]+1，0<j<i且a[j]<a[i])，

结果为max(dp[i])

由于需要遍历i之前的所有dp[j]，所以是一个二重循环，复杂度O(n2)。

LIS的转移方程不那么直观，上一篇数字三角形中dp[i]的计算会依赖dp[i-1]，这也是很多时候会用到的模式，而LIS需要一个循环才能算出dp[i]，依赖dp[j(0<j<i)]。说明dp在转移时可能形式多样，dp[i]肯定依赖i之前的dp，但是没有定式，逻辑可能比较复杂，也因此使得DP算法灵活多变。

LIS除了计算最大长度，有时候可能需要记录最长序列的值，采用一个表记录即可，path[i]=j表示i的前驱节点是j，其实对于每一个节点，在更新的过程中只可能有一个前驱节点，因此是不会存在问题的。

源代码：

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <set>
#include <limits.h>
#include <vector>
#include <string>
#include <bitset>
using namespace std;

#ifdef __APPLE__
#define printfd printf
#else
#define printfd
#endif

#define MAX_SIZE 1000000

int main()
{
#ifdef __APPLE__
    freopen("test.txt", "r", stdin);
#endif
    int n;
    scanf("%d", &n);

    vector<int> v(n+1, 0);
    for(int i=1; i<=n; ++i){
        scanf("%d", &v[i]);
    }

    int dp[MAX_SIZE] = {0};
    int path[MAX_SIZE] = {0};
    int max = 0;
    int pos = 0;

    for(int i=1; i<=n; ++i){
        //dp[i] = max(0,dp[j]) + 1
        int m = 0;
        for(int j=1; j<i; ++j){
            if(v[j] < v[i]){
                if(dp[j] > m){
                    path[i] = j;
                    //printfd("j->i %d->%d\n", j, i);
                }
                m = std::max(m, dp[j]);
            }
        }
        dp[i] = m + 1;
        if(dp[i] > max){
            pos = i;
        }
        max = std::max(dp[i], max);
        printfd("dp[%d]=%d\n", i, dp[i]);
    }

    printf("%d\n", max);
    while(pos > 0){
        printfd("%d ", pos);
        pos = path[pos];
    }
    printfd("\n");

    return 0;
}

写完后想到一个扩展题：这里求的是上升子序列，如果求有序子序列呢？有序是指既可能上升又可能下降的序列，有兴趣的同学可以多思考下哈~

下一篇我们接着看LCS，最长公共子序列。