动态规划（Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

最长上升子序列（LIS）

给出一个序列 a1,a2,...,an−1,ana_1, a_2, ...,a_{n-1}, a_n ，求其最长不下降（或上升）子序列。

求最长上升子序列（LIS）的算法是Yukko介绍给我的第一个算法。

解决方案（ O(n2)O(n^2) ）

状态设计：

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

状态转移方程：

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

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
#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;
}

解决方案（ O(nlog⁡n)O(n\log_{}{n}) ）

例题

洛谷 P1020 | [NOIP1999 普及组] 导弹拦截

洛谷 P1091 | [NOIP2004 提高组] 合唱队形

最长公共子序列（LCS）

模板题：洛谷 P1439 | [模板]最长公共子序列

题目描述

给出 1,2,…,n1,2,\ldots,n 的两个排列 P1P_1 和 P2P_2 ，求它们的最长公共子序列。

输入格式

第一行是一个数 nn 。

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

输出格式

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

输入输出样例

输入 #1
1
2
3
5 
3 2 1 4 5
1 2 3 4 5
输出 #1
1
3
数据规模与约定
  • 对于 50%50\% 的数据， n≤103n \le 10^3 ；
  • 对于 100%100\% 的数据， n≤105n \le 10^5 。

解决方案

状态设计：

dp[i][j]dp[i][j] 表示 P1P_1 前 ii 位， P2P_2 前 jj 位的最长公共子序列长度。

状态转移方程：

dp[i][j]={max(dp[i][j],dp[i−1][j−1]+1)if P1[i]=P2[j]max(dp[i−1][j],dp[i][j−1])if P1[i]≠P2[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} 

1

请参阅