SDUTOJ1299（动态规划）：最长上升子序列

SDUTOJ1299（动态规划）：最长上升子序列

========================

题目如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
最长上升子序列
Description
一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1<= i1 < i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8)。

你的任务，就是对于给定的序列，求出最长上升子序列的长度。
Input
输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。
Output
最长上升子序列的长度。
Sample
Input 
7
1 7 3 5 9 4 8
Output 
4

我的代码

1
//比较简单，这里做记录即可

心得： 这是一道比较经典的动规题，难度低。

思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
我们要求最长上升子序列的长度，自然要挨个数字来寻找，这时我们用dp[i]来表示用i个数字结尾的最长上升子序列的长度。
样例 1 7 3 5 9 4 8
dp[i] 1 2 2 3 3 …
dp[2]：
dp[2]=dp[1]+1;
dp[3]:
dp[3]=dp[1]+1;
dp[4]:
dp[4]=dp[1]+1;
dp[4]=dp[3]+1;
这时我们发现了什么规律呢？
没错从第一位数字开始寻找，找到一个比当前的数小的数就+1更新一下，直到遍历到当前数字。
我们就得到状态转移方程
dp[i]=max( dp[j] + 1, dp[i] ) 0<j<i;

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;

const int N=1000;
int a[N],dp[N];

int main()
{
    int n;
    int res=0;
    cin>> n;
    dp[0]=0;
    a[0]=-1;  //注意这里为什么要让a[0]=-1?还是说让a[0]小于某个数就行？  继续往下看
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        for(int j=0;j<i;j++){
            if(a[j]<a[i]){     //这里我们第一次发现了a数组的比较  j从0开始也就发现了上面关于a[0]的问题
            //我们注意到a[i]任意一个数是大于等于0的而a[0]是负数  结合下面的代码我们发现其目的就是在于解决最小上升子序列的长度为1的情况
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
        res=max(res,dp[i]);
    }
    cout<<res<<endl;
    return 0;
}

题目链接：https://acm.sdut.edu.cn/onlinejudge3/problems/1299