状态设计：#

$dp[i]$ 表示以第 $i$ 个数结尾的最长上升子序列的最长长度。

状态转移方程：#

$dp[i]= max(dp[j])+1 \quad (1≤j＜i， 且a[i]>a[j])$

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 100500;
int n, ans;
int a[maxn], dp[maxn];
int main()
{
	scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &a[i]);
        dp[i] = 1;	
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < i; j++)
        {
            if (a[i] > a[j] && dp[i] < dp[j] + 1)	//如果a[i] > a[j]，则a[i]可以接在以a[j]结尾的上升子序列后面
                dp[i] = dp[j] + 1;	//如果dp[i] < dp[j] + 1，则可以用dp[j] + 1来更新dp[i]
        }
        ans = max(ans, dp[i]);	//取dp[i]的最大值来作为ans
    }
    printf("%d", ans);
    return 0;
}

题目描述#

给出 $1,2,\ldots,n$ 的两个排列 $P_1$ 和 $P_2$ ，求它们的最长公共子序列。

输入格式#

第一行是一个数 $n$ 。

接下来两行，每行为 $n$ 个数，为自然数 $1,2,\ldots,n$ 的一个排列。

输出格式#

一个数，即最长公共子序列的长度。

输入输出样例#

5 
3 2 1 4 5
1 2 3 4 5

3

状态设计：#

$dp[i][j]$ 表示 $P_1$ 前 $i$ 位， $P_2$ 前 $j$ 位的最长公共子序列长度。

状态转移方程：#

$dp[i][j]=\begin{cases}max(dp[i][j], dp[i-1][j-1] + 1) &\text{if } P_1[i]=P_2[j] \\ max(dp[i-1][j], dp[i][j-1]) &\text{if } P_1[i]\not =P_2[j] \end{cases}$