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

￡神魔★判官ぃ 2021-09-07 06:03 389阅读 0赞

### 文章目录 ###

*   *  问题描述
 *  一.简单推论（非0 n情况）
 *   *  1.问题分析
     *  2.状态转移方程
     *  3.参考代码
     *  4.运行结果
 *  二.严谨推论
 *   *  1.问题分析
     *  2.状态转移方程
     *  3.参考代码
     *  4.运行结果

## 问题描述 ##

> 最长上升子序列(LIS):  
> 给定长度为n的序列，从中选取一个子序列，这个子序列需要单调递增  
> 问最长上升子序列(LIS)的长度  
> eg：1，5，2，3，11，7，9  
> 则LIS序列为:1，2，3，7，9，长度为5

# 一.简单推论（非0 n情况） #

## 1.问题分析 ##

设计状态dp\[x\]为以a\[x\]结尾的LIS长度，那么整体的LIS长度就为dp数组的最大值。  
以eg为例：  
a\[n\]为序列数组，dp\[n\]为LIS数组。  
dp\[1\]=以a\[1\]，即以1结尾的LIS长度，即为1；  
dp\[2\]=以a\[2\]，即以5结尾的LIS长度，即为2；  
dp\[3\]=以a\[3\]，即以2结尾的LIS长度，这里我们注意到，2小于5，所以\{1，5，2\}的LIS长度=2，也就是dp\[2\],所以在a\[3\]<a\[2\]的情况下dp\[3\]=dp\[2\];  
dp\[4\]=以a\[4\]，即以3结尾的LIS长度，这里我们注意到，3大于2，所以\{1，5，2，3\}的LIS长度=3，也就是dp\[3\]+1,所以在a\[4\]>a\[3\]的情况下dp\[4\]=dp\[3\]+1;  
dp\[5\]=以a\[5\]，即以11结尾的LIS长度，这里我们注意到，11大于3，所以\{1，5，2，3，11\}的LIS长度=4，也就是dp\[4\]+1,所以在a\[5\]>a\[4\]的情况下dp\[5\]=dp\[4\]+1;  
dp\[6\]=以a\[6\]，即以7结尾的LIS长度，这里我们注意到，7小于11，所以\{1，5，2，3，11，7\}的LIS长度=4，也就是dp\[5\],所以在a\[6\]<a\[5\]的情况下dp\[6\]=dp\[5\];  
dp\[7\]=以a\[7\]，即9结尾的LIS长度，这里我们注意到，9大于7，所以\{1，5，2，3，11，7，9\}的LIS长度=5，也就是dp\[6\]+1,所以在a\[7\]>a\[6\]的情况下dp\[7\]=dp\[6\]+1;  
根据以上推导，我们就得到了dp数组\{1，2，2，3，4，4，5\}，dp数组的最大值5即我们所求的a数组的LIS长度。

## 2.状态转移方程 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwMjE2Mjcw_size_16_color_FFFFFF_t_70]

## 3.参考代码 ##

#include<bits/stdc++.h>
    using namespace std;
    int main()
    { 
        int n;
        cin>>n;
        int a[n+1],dp[n+1];
        a[0]=0,dp[0]=0;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)
        { 
            dp[i]=1;
            if(a[i]>a[i-1])dp[i]=dp[i-1]+1;
            else dp[i]=dp[i-1];
        }
        int maxdp=1;
        for(int i=1;i<=n;i++)
        { 
            maxdp=max(maxdp,dp[i]);
        }
        cout<<maxdp;
    }

## 4.运行结果 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwMjE2Mjcw_size_16_color_FFFFFF_t_70 1]

# 二.严谨推论 #

## 1.问题分析 ##

设计状态dp\[x\]为以a\[x\]结尾的LIS长度，那么整体的LIS长度就为dp数组的最大值。在求dp\[x\]的时候考虑比a\[x\]小的每一个a\[i\]的dp\[i\]+1。  
以eg为例：  
a\[n\]为序列数组，dp\[n\]为LIS数组。  
dp\[1\]=以a\[1\]，即以1结尾的LIS长度，即为1；  
dp\[2\]=以a\[2\]，即以5结尾的LIS长度，即为2；  
dp\[3\]=以a\[3\]，即以2结尾的LIS长度，这里我们注意到，2小于5，2大于1，所以\{1，5，2\}的LIS长度=2，也就是dp\[1\]+1,所以在a\[2\]>a\[1\]的情况下dp\[3\]=dp\[1\]+1;  
dp\[4\]=以a\[4\]，即以3结尾的LIS长度，这里我们注意到，3大于2，3大于1，所以\{1，5，2，3\}的LIS长度=3，也就是max(dp\[1\],dp\[2\])+1,所以在a\[4\]>a\[3\]，a\[4\]>a\[1\]的情况下dp\[4\]=max(dp\[1\],dp\[2\])+1；  
dp\[5\]=以a\[5\]，即以11结尾的LIS长度，这里我们注意到，11大于3，11大于2，11大于5，11大于1，所以\{1，5，2，3，11\}的LIS长度=4，也就是max\{dp\[1\],dp\[2\],dp\[3\],dp\[4\]\}+1,所以在a\[5\]>a\[4\]，a\[5\]>a\[3\]，a\[5\]>a\[2\]，a\[5\]>a\[1\]的情况下dp\[5\]=max\{dp\[1\],dp\[2\],dp\[3\],dp\[4\]\}+1;  
同理推导。。。。。。  
根据以上推导，我们就得到了dp数组\{1，2，2，3，4，4，5\}，dp数组的最大值5即我们所求的a数组的LIS长度。

## 2.状态转移方程 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwMjE2Mjcw_size_16_color_FFFFFF_t_70 2]

## 3.参考代码 ##

#include<bits/stdc++.h>
    using namespace std;
    int main()
    { 
        int n;
        cin>>n;
        int a[n+1],dp[n+1];
        a[0]=0,dp[0]=0;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)
        { 
            dp[i]=1;
            for(int j=1;j<=i;j++)
            { 
                if(a[j]<a[i])dp[i]=max(dp[i],dp[j]+1);
            }
        }
        int maxdp=1;
        for(int i=1;i<=n;i++)
        { 
            maxdp=max(maxdp,dp[i]);
        }
        cout<<maxdp;
    }

## 4.运行结果 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwMjE2Mjcw_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwMjE2Mjcw_size_16_color_FFFFFF_t_70]: /images/20210827/adc25fb5fa154a97beccff022c9b2123.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwMjE2Mjcw_size_16_color_FFFFFF_t_70 1]: /images/20210827/c21774fe3e7e4a30819d847ec6ec2394.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwMjE2Mjcw_size_16_color_FFFFFF_t_70 2]: /images/20210827/c100d8f9f512442fbd1e4fa98fc983fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwMjE2Mjcw_size_16_color_FFFFFF_t_70 3]: /images/20210827/e79097c68bf14532874e2df356195e12.png