动态规划---最长上升子序列问题(O(nlogn),O(n^2))

LIS(Longest Increasing Subsequence)最长上升子序列 或者 最长不下降子序列。很基础的题目,有两种算法,复杂度分别为O(n*logn)和O(n^2) 。

*********************************************************************************

先回顾经典的O(n^2)的动态规划算法:

设a[t]表示序列中的第t个数,dp[t]表示从1到t这一段中以t结尾的最长上升子序列的长度,初始时设dp[t] = 0(t = 1, 2, ..., len(A))。则有动态规划方程:dp[t] = max{1, dp[j] + 1} (j = 1, 2, ..., t - 1, 且a[j] < a[t])。

一般若从a[t]开始,此时最长不下降子序列应该是按下列方法求出的: 
 在a[t+1],a[t+2],...a[n]中,找出一个比a[t]大的且最长的不下降子序列,作为它的后继。

代码实现如下:

#include<iostream>
using namespace std;
#define max(a,b) a>b?a:b
int main()
{
    int n, i, j, dp[101], x[101], max_len;
    while (cin >> n)
    {
        for (i = 0; i < n; i++)
            cin >> x[i];
        dp[0] = 1;//表示以x[0]为子序列最右边的长度位1
        for (i = 1; i < n; i++)
        {
            dp[i] = 1;//初始化每种情况最小值为1
            for (j = 0; j < i; j++)
            {
                if (x[i]>x[j] && dp[j] + 1>dp[i])//从0-i进行扫描,查找边界小于当前最优解长度相等的解优化最优解
                    dp[i] = dp[j] + 1;//如果允许子序列相邻元素相同  x[i]>=x[j]&&dp[j]+1>dp[i];
            }
        }
        for (i = max_len = 0; i < n; i++)
            max_len = max(max_len, dp[i]);//等到最大子序列长度
        cout << max_len << endl;
    }
    return 0;
}

最长上升子序列O(nlogn)解法

在一列数中寻找一些数,这些数满足:任意两个数a[i]和a[j],若i<j,必有a[i]<a[j],这样最长的子序列称为最长递增子序列。

设dp[i]表示以i为结尾的最长递增子序列的长度,则状态转移方程为:

dp[i] = max{dp[j]+1}, 1<=j<i,a[j]<a[i].

考虑两个数a[x]和a[y],x<y且a[x]<a[y],且dp[x]=dp[y],当a[t]要选择时,到底取哪一个构成最优的呢?显然选取a[x]更有潜力,因为可能存在a[x]<a[z]<a[y],这样a[t]可以获得更优的值。在这里给我们一个启示,当dp[t]一样时,尽量选择更小的a[x].

按dp[t]=k来分类,只需保留dp[t]=k的所有a[t]中的最小值,设g[k]记录这个值,g[k]=min{a[t],dp[t]=k}。

这时注意到g的两个特点(重点):

1. g[k]在计算过程中单调不升;

2. g数组是有序的,g[1]<g[2]<..g[n]。

利用这两个性质,可以很方便的求解:

(1).设当前已求出的最长上升子序列的长度为len(初始时为1),每次读入一个新元素x:

(2).若x>g[len],则直接加入到d的末尾,且len++;(利用性质2)

否则,在g中二分查找,找到第一个比x小的数g[k],并g[k+1]=x,在这里x<=g[k+1]一定成立(性质1,2)。

代码实现如下:

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 50001;
int binary_search(int key, int *g, int low, int high)
{
    while (low <= high)
    {
        int mid = (low + high) >> 1;
        if (key > g[mid] && key <= g[mid + 1])
            return mid;
        else if (key > g[mid])
            low = mid + 1;
        else
            high = mid - 1;
    }
    return 0;
}
int main()
{
    int i, j, a[maxn], g[maxn], n, len;
    while (cin >> n)
    {
        memset(g, 0, sizeof(g));
        for (i = 0; i < n; i++)
            cin >> a[i];
        g[1] = a[0], len = 1;//初始化子序列长度为1,最小右边界
        for (i = 1; i < n; i++)
        {
            if (g[len] < a[i])//(如果允许子序列相邻元素相同 g[len]<=a[i],默认为不等)
                j = ++len; //a[i]>g[len],直接加入到g的末尾,且len++
            else
                j = binary_search(a[i], g, 1, len) + 1;
            g[j] = a[i];//二分查找,找到第一个比a[i]小的数g[k],并g[k+1]=a[i]
        }
        cout << len << endl;
    }
    return 0;
}

例题分析:(swust oj 126 低价购买)

低价购买

Time limit(ms): 1000       Memory limit(kb): 65535

“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者,你必须遵循以下的问题建议:“低价购买;再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下,求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(216范围内的正整数),你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买;再低价购买”的原则。写一个程序计算最大购买次数。
这里是某支股票的价格清单: 
日期 1 2 3 4 5 6 7 8 9 10 11 12 
价格 68 69 54 64 68 64 70 67 78 62 98 87 
最优秀的投资者可以购买最多4次股票,可行方案中的一种是: 
日期 2 5 6 10 
价格 69 68 64 62

Description

第1行: N (1 <= N <= 5000),股票发行天数 
第2行: N个数,是每天的股票价格。

Input

输出文件仅一行包含两个数:最大购买次数和拥有最大购买次数的方案数(<=231)当二种方案“看起来一样”时(就是说它们构成的价格队列一样的时候),这2种方案被认为是相同的。

Output

1

2

3

12

68 69 54 64 68 64 70 67 78 62 98 87

Sample Input

1

4 2

分析:在扫描[1,i-1]寻找最优解时,如果当前解与已知最优解相同,就进行累加;如果更大,就覆盖之前的结果。对于重复方案的判断,可以比较已
知最优解的末尾和和当前解的末尾,两个价格如果相同,那么就不能进行累加,而应该选取更靠后的一个。显然靠后的价格会有不少于靠前的
价格的方案数,例如序列3,2,3,2,1:
num[2]=1,num[4]=2。
为了方便起见,可以从后往前扫描,即i-1 to 1,并用t记录最近一个最优解的price,只有小于t的price[j]才进行累加和更新。

AC 代码:

#include<iostream>
using namespace std;
int price[5001], dp[5001], num[5001];
int main()
{
    int n, i, j, t;
    cin >> n;
    for (i = 0; i < n; i++)
        cin >> price[i];
    for (i = 0; i <= n; i++)
    {
        num[i] = 1;
        t = 0x3f3f3f3f; //判断是否为相同方案的变量
        for (j = i - 1; j >= 0; j--)
        if (price[j]>price[i])
        {
            if (dp[j] >= dp[i])
            {
                t = price[j];
                dp[i] = dp[j] + 1;
                num[i] = num[j];
            }
            else if (dp[j] + 1 == dp[i] && price[j] < t)
            {
                t = price[j];
                num[i] += num[j];
            }
        }
    }
    cout << dp[n] << ‘ ‘ << num[n] << endl;;
    return 0;
}

不得不说一句dp是个神奇而强大的思想~~~~

时间: 02-19

动态规划---最长上升子序列问题(O(nlogn),O(n^2))的相关文章

动态规划 - 最长上升子序列问题

原文  http://xuanwo.org/2015/07/31/dp-lis/ 主题 动态规划 介绍 最长上升子序列问题,也就是 Longest increasing subsequence ,缩写为LIS .是指在一个序列中求长度最长的一个上升子序列的问题,是动态规划中一个相当经典问题.在这里我们可以看到,这个上升实质上就是一个对 < 进行定义的过程,所以我们求解的其实是一类问题,也就是在给定序列中求解长度最长的符合某一性质的子序列的问题.在下面总结的过程中,我还是以递增为例进行阐述. O(

动态规划-最长公共子序列

(1).问题描述:给出2个序列,x是从1到m,y是从1到n,找出x和y的最长公共子序列? x:A B C B D A B y:B D C A B A 则:最长公共子序列长度为4,BDAB BCAB BCBA均为LCS(最长公共子序列): 模型实现图: (2).问题解决 代码实现了最长公共子序列的长度 #include<stdio.h> #define N    10 int LCS(int *a, int count1, int *b, int count2); int LCS(int *a,

动态规划 - 最长公共子序列(LCS)

最长公共子序列也是动态规划中的一个经典问题. 有两个字符串 S1 和 S2,求一个最长公共子串,即求字符串 S3,它同时为 S1 和 S2 的子串,且要求它的长度最长,并确定这个长度.这个问题被我们称为 最长公共子序列问题. 与求最长递增子序列一样,我们首先将原问题分割成一些子问题,我们用 dp[i][j]表示 S1 中前 i 个字符与 S2 中前 j 个字符分别组成的两个前缀字符串的最 长公共子串长度. 显然的,当 i. j 较小时我们可以直接得出答案,如 dp[0][j]必 等于 0.那么,

nlog(n)解动态规划--最长上升子序列(Longest increasing subsequence)

最长上升子序列LIS问题属于动态规划的初级问题,用纯动态规划的方法来求解的时间复杂度是O(n^2).但是如果加上二叉搜索的方法,那么时间复杂度可以降到nlog(n).  具体分析参考:http://blog.chinaunix.net/uid-26548237-id-3757779.html 代码: #include <iostream> using namespace std; int LIS_nlogn(int *arr, int len) { int *LIS = new int[len

动态规划 最长公共子序列 王子和公主 Prince and Princess UVa 10635

#include <iostream> #include <algorithm> using namespace std; const int maxn = 250 * 250; int main(){ char T; cin >> T; for (char k = 0; k < T;k++) { int n, p, q; cin >> n >> p >> q; int num[maxn]; memset(num, 0, siz

最长公共子序列 时间 O(NlogN) 空间 O(N)

参考:https://segmentfault.com/a/1190000003819886 在给定的一个序列中,我们可以得到: (1)不同长度 (2)且保证该升序序列在同长度升序序列中末尾最小的升序序列. 这些序列都是未来有可能成为最长序列的候选人.这样,每来一个新的数,我们便按照以下规则更新这些序列 如果nums[i]比所有序列的末尾都大,(或等于最大末尾,看题目要求),说明有一个新的不同长度序列产生,我们把最长的序列复制一个,并加上这个nums[i]. 如果nums[i]比所有序列的末尾都

lis最长上升子序列 (kuangbin nlogn)

1 int arr[maxn],ans[maxn],len; 2 3 void Lis() 4 { 5 ///ans为序列数组 6 memset(arr,0,sizeof(arr)); 7 memset(ans,0,sizeof(ans)); 8 ans[1] = arr[1]; 9 len=1; 10 for(int i=2; i<=n; ++i){ 11 if(arr[i]>ans[len])///严格上升 12 ans[++len]=arr[i]; 13 else{ 14 int pos

LIS最长上升子序列O(n^2)与O(nlogn)的算法

动态规划 最长上升子序列问题(LIS).给定n个整数,按从左到右的顺序选出尽量多的整数,组成一个上升子序列(子序列可以理解为:删除0个或多个数,其他数的顺序不变).例如序列1, 6, 2, 3, 7, 5,可以选出上升子序列1, 2, 3, 5,也可以选出1, 6, 7,但前者更长.选出的上升子序列中相邻元素不能相等. 最容易想到的办法就是用一个数组f[i]保存到达第i个数的LIS 初始化f[i]=1 更新 f[i]=max{f[j]+1,f[i]|a[j]<a[i],1<=j<i} 即

[ An Ac a Day ^_^ ] HDU 1257 基础dp 最长上升子序列

最近两天在迎新 看来只能接着水题了…… 新生培训的任务分配 作为一个有担当的学长 自觉去选了动态规划…… 然后我觉得我可以开始水动态规划了…… 今天水一发最长上升子序列…… kuangbin有nlogn的模板…… 自己写一发原来学的吧…… 1 #include<stdio.h> 2 #include<iostream> 3 #include<algorithm> 4 #include<math.h> 5 #include<string.h> 6