`
lingyibin
  • 浏览: 196277 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

最长上升子序列问题的几种解法

阅读更多

拿POJ 2533来说。

Sample Input

7
1 7 3 5 9 4 8

Sample Output

4

从输入的序列中找出最长的上升子序列(LIS)。

这题一看,是一道典型的DP问题(就是动态规划),可以用dfs,深度优先遍历来解,如下代码:

#include<iostream>
#include<stack>
using namespace std;

 

int n;
int* a;
stack<int> s;
int count=0;
int best=0;


void dfs(int i)
{
  if(i==n)
  {
    if(s.size()>best) best=s.size();
    return;
  }
  if(s.empty()||a[i]>s.top())
  {
    s.push(a[i]);
    dfs(i+1);
    s.pop();
  }
  if(s.size()+n-i-1>best) dfs(i+1);


int main()
{
  while(cin>>n)

{
   int i;
  a=new int[n];
  for(i=0;i<n;i++)
  {
    cin>>a[i];
  }
 dfs(0);
 cout<<best<<endl;
 delete [] a;

}
 return 0;
}

 

其实为了简化代码以及算法效率,我们可以用数据组来代替递归。。。下面我就给出LIS的DP的数据组形式的解法:

(懒得写了,就拿个别人的代码来展示吧)

#include <iostream>
#define SIZE 1001
 
using namespace std;
 
int main()
{
    int i, j, n, max;
    /* a[i]表示输入第i个元素 */
    int a[SIZE];
    /* d[i]表示以a[i]结尾的最长子序列长度 */
    int d[SIZE];
 
    while(cin >> n)
 {
  for (i = 1; i <= n; i++)
  {
   cin >> a[i];
  }
 
  max = 0;
  for (i = 1; i <= n; i++)
  {
   d[i] = 1;
   for (j = 1; j <= i - 1; j++)
   {
    if (a[j] < a[i] && d[i] < d[j] + 1) //这边,要注意 d[i] < d[j] + 1这个条件的限制,它是为了在

                                               //连续几个 d[i]相同时 只加一次
    {
     d[i] = d[j] + 1;
    }
   }
   /* 记录最长子序列 */
   if (d[i] > max) max = d[i];
  }
 
  cout << max << endl;
 }
 
    //system("pause");
    return 0;
}

(作者的解释:)令A[i]表示输入第i个元素,D[i]表示从A[1]到A[i]中以A[i]结尾的最长子序列长度。对于任意的0 <  j <= i-1,如果A(j) < A(i),则A(i)可以接在A(j)后面形成一个以A(i)结尾的新的最长上升子序列。对于所有的 0 <  j <= i-1,我们需要找出其中的最大值。

DP状态转移方程:

D[i] = max{1, D[j] + 1} (j = 1, 2, 3, ..., i-1 且 A[j] < A[i])

解释一下这个方程,i, j在范围内:

如果 A[j] < A[i] ,则D[i] = D[j] + 1

如果 A[j] >= A[i] ,则D[i] = 1

 

其实上面的方法的复杂度都达到了O(n^2)的数量级,有没有更好的解法呢?

有,用栈。

这个解法不是我想的,从网上学来的,这里面与大家分享一下。这个算法的复杂度只有O(nlogn),在有大量数据的情况下,这算法效率极高。。。

(摘录原作者的话)

 

这个算法其实已经不是DP了,有点像贪心。至于复杂度降低其实是因为这个算法里面用到了二分搜索。本来有N个数要处理是O(n),每次计算要查找N次还是O(n),一共就是O(n^2);现在搜索换成了O(logn)的二分搜索,总的复杂度就变为O(nlogn)了。

这个算法的具体操作如下(by RyanWang):

开一个栈,每次取栈顶元素top和读到的元素temp做比较,如果temp > top 则将temp入栈;如果temp < top则二分查找栈中的比temp大的第1个数,并用temp替换它。 最长序列长度即为栈的大小top。

这也是很好理解的,对于x和y,如果x < y且Stack[y] < Stack[x],用Stack[x]替换Stack[y],此时的最长序列长度没有改变但序列Q的''潜力''增大了。

举例:原序列为1,5,8,3,6,7

栈为1,5,8,此时读到3,用3替换5,得到1,3,8; 再读6,用6替换8,得到1,3,6;再读7,得到最终栈为1,3,6,7。最长递增子序列为长度4。

 

我想,当出现1,5,8,2这种情况时,栈内最后的数是1,2,8不是正确的序列啊?难道错了?

分析一下,我们可以看出,虽然有些时候这样得不到正确的序列了,但最后算出来的个数是没错的,为什么呢?

想想,当temp>top时,总个数直接加1,这肯定没错;但当temp<top时呢? 这时temp肯定只是替换了栈里面的某一个元素,所以大小不变,就是说一个小于栈顶的元素加入时,总个数不变。这两种情况的分析可以看出,如果只求个数的话,这个算法比较高效。但如果要求打印出序列时,就只能用DP了。

用该算法完成POJ2533的具体代码如下:

 

 

#include <iostream>
#define SIZE 1001
 
using namespace std;
 
int main()
{
    int i, j, n, top, temp;
    int stack[SIZE];
    while(cin >> n)
   {
    top = 0;
    /* 第一个元素可能为0 */
    stack[0] = -1;
    for (i = 0; i < n; i++)
    {
        cin >> temp;
        /* 比栈顶元素大数就入栈 */
        if (temp > stack[top])
        {
            stack[++top] = temp;
        }
        else
        {
            int low = 1, high = top;
            int mid;
            /* 二分检索栈中比temp大的第一个数 */
            while(low <= high)
            {
                mid = (low + high) / 2;
                if (temp > stack[mid])
                {
                    low = mid + 1;
                }
                else
                {
                    high = mid - 1;
                }
            }
            /* 用temp替换 */
            stack[low] = temp;
        }
    }
 
    /* 最长序列数就是栈的大小 */
    cout << top << endl;
  } 
    return 0;
}

分享到:
评论

相关推荐

    最长公共子序列问题.md

    最长公共子序列问题(LCS)是计算机科学中的一种基础问题,它在算法设计与分析领域占有重要地位。LCS问题主要解决的是如何找到两个序列共有的最长子序列的问题,该子序列在两个序列中出现的顺序一致,但不需要连续。...

    求一个整数序列的最长递增子序列.doc

    【最长递增子序列(LIS)问题】 最长递增子序列(Longest Increasing Subsequence,简称LIS)是计算机科学中的一个重要问题,特别是在算法设计和分析中。它要求找到一个给定序列中的一个子序列,使得这个子序列是...

    动态规划算法中对子序列的一些模板

    在本主题“动态规划算法中对子序列的一些模板”中,我们将深入探讨几种与子序列相关的经典问题及其解决方案。 1. **最长公共子序列(Longest Common Subsequence, LCS)** - LCS问题是寻找两个或多个序列中的最...

    几道经典DP问题的解法

    最长公共子串问题是另一个典型的动态规划应用场景,旨在寻找两个字符串中的最长公共连续子序列。这一问题在生物信息学、文本处理等领域有着重要应用。 #### 解题思路 在二维矩阵`C[i,j]`中,根据以下规则进行状态...

    dp总结文件

    - **算法思路**:先求出以每个数为结尾的最长上升子序列长度,然后按字典序排序输出。 ### 4. 区间 DP:最小中间和 #### 问题描述 给定一个正整数序列 a1, a2, ..., an,不改变序列中的每个元素在序列中的位置,...

    动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。

    它通过自底向上的计算和存储子问题解,有效地减少了计算复杂性,解决了许多实际问题,如最短路径、背包问题、最长公共子序列等。理解和掌握动态规划,对于解决计算机科学中的优化问题具有重大意义。

    暴力、递归与分治、动态规划、贪心算法、回溯经典习题

    这类习题有助于培养总结经验、状态转移的思维能力,如背包问题、最长公共子序列等。 4. 贪心算法习题 贪心算法通过局部最优选择来近似获得全局最优解,在某些场景下可以极高效地解决问题。这类习题有助于启发我们从...

    动态规划算法优化

    ##### 案例1:最长递增子序列问题 **问题描述**:给定一个整数序列,找出其中最长的递增子序列的长度。 **经典动态规划解法**: 设 `F[i]` 表示以第 `i` 个元素结尾的最长递增子序列的长度,则有状态转移方程: \...

    第六届蓝桥杯软件类校赛真题(Java语言A组).pdf

    以上几个知识点分别涵盖了最长公共子序列问题、圆周率π的计算以及数值逼近方法等IT领域的基础知识和技术点。这些知识点不仅在比赛中非常重要,也是学习计算机科学和编程的基础。希望通过对这些题目的分析,能够帮助...

    2024Leetcode最新解题笔记

    动态规划求最长上升子序列**:这是一个经典的动态规划问题,旨在寻找给定序列中最长的递增子序列,通常使用dp数组来记录每一步的最优解。 #### 二、回溯算法 **回溯算法**是一种通过尝试解决问题的不同可能性来...

    动态规划专题讲解

    最长不下降子序列问题要求从一个无序的整数数组序列中寻找一个最长的子序列,使得这个子序列中的数是按非降序排列的。动态规划算法可以有效地求解这类问题,虽然存在时间复杂度为O(n^2)的常规解法,但也有时间复杂度...

    第十八届西南科技大学ACM程序设计竞赛题解

    对于求解某数列的最长上升子序列问题,有一个动态规划+二分的解法,主要步骤如下:1.定义一个动态数列,初始为空2.从左到右遍历所有元素 2.1 获取当前遍历到的元素 2.2 如果该元素比中所有元素大(为空时也成立),则...

    湖南大学复习算法分析期末答案大题.doc

    湖南大学这道期末试题涵盖了几个关键的算法概念,包括机器调度问题、单源最短路径问题和最长公共子序列问题,这些都是算法分析中的经典主题。 1. **机器调度问题**: - **问题描述**:这是一个典型的作业调度问题...

    删除回文子序列1

    题目中提到,由于字符串只包含两种字符,任何单一字符的子序列都是回文的。这意味着,如果字符串本身是回文,我们只需要删除一次即可使其变为空;如果不是回文,我们可以通过删除所有一个字符(如'a'),然后删除...

    动态规划算法综述.docx

    为了更好地理解动态规划的应用,我们可以通过一些具体的例子来进行分析,比如最长公共子序列问题、背包问题等。这些问题是动态规划的经典应用场景,通过对这些案例的学习可以帮助加深对动态规划算法的理解。 **1. ...

    算法设计与分析:第5章 动态规划法.pdf

    6. 最长公共子序列问题:寻找两个序列最长公共子序列的问题,常用于文件比较、生物信息学中蛋白质序列比较等。 7. 流水作业问题:在工业工程中,寻找完成工作流的最优时间排程,其中每个作业有特定的执行时间,并且...

    动态规划解题方法.doc

    - **最大值或最小值问题**:例如,找到一条从左上角到右下角的最大路径和(如二维数组中的斐波那契数列问题)或者寻找最长上升子序列。 - **存在性问题**:判断是否存在某种解决方案,如石头游戏(博弈论问题),...

    「代码随想录」动态规划专题精讲(v1.1).pdf

    4. 最长公共子序列:给定两个序列,求它们的最长公共子序列的长度。 5. 最长回文子串:要求找出字符串中的最长回文子串。 针对以上问题,动态规划可以使用“状态”和“状态转移方程”来描述问题的解决过程。状态是...

    算法设计策略 - 07 动态规划.pdf

    - 最长公共子序列(LCS):找到两个序列共有最长子序列的问题。 - 每对结点的最短路径:在一个图中找到每对顶点之间的最短路径。 - 投资问题:确定最优的投资策略,使利润最大化。 - 最优二叉搜索树:构建一种二叉...

Global site tag (gtag.js) - Google Analytics