专栏首页ACM算法日常DP专题 | LIS POJ - 2533

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,最长公共子序列。

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:dansen

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 最长上升子序列(LIS)算法

    LIS(Longest Increasing Subsequence)最长上升子序列 一个数的序列bi,当b1 < b2 < … < bS的时候,我们称这个序列...

    ACM算法日常
  • 字符串的距离(动态规划) - leetcode 72

    ,因为在刷leetcode的动态规划专题。动态规划虽然定义很简单,但是对于复杂的动态规划题目,很多时候还是很棘手的。

    ACM算法日常
  • 石子合并(区间动态规划)- NYOJ 737

    有N堆石子排成一排,每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆,每次合并花费的代价为这两堆石子的...

    ACM算法日常
  • Leetcode 70 Climbing Stairs

    You are climbing a stair case. It takes n steps to reach to the top. Each time...

    triplebee
  • LeetCode 516. 最长回文子序列(动态规划)

    Michael阿明
  • 穿上衣服我就不认识你了?来聊聊最长上升子序列

    最长上升子序列是一个很经典的算法题。有的会直接让你求最长上升子序列,有的则会换个说法,但最终考察的还是最长上升子序列。那么问题来了,它穿上衣服你还看得出来是么?

    lucifer210
  • 【POJ 2250】Compromise(最长公共子序列LCS)

    题目 字符串的LCS,输出解我比较不会,dp的时候记录从哪里转移来的,之后要一步一步转移回去把解存起来然后输出。

    饶文津
  • LintCode 最长公共子序列题目分析代码

    典型的动态规划问题 dp[i][[j]:表示前i个和前j个字符最大LCS 当A[i] = B[i]的时候: 那么显然dp[i][j] = dp[i-1][...

    desperate633
  • 画解算法:70. 爬楼梯

    https://leetcode-cn.com/problems/climbing-stairs/

    灵魂画师牧码
  • LeetCode 123. Best Time to Buy and Sell Stock III

    https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/

    ShenduCC

扫码关注云+社区

领取腾讯云代金券