一、概念
以下内容摘自代码源
- 两个要求
- 最优子结构：大问题的解可以从小问题的解推出，在问题的拆解过程中不能无限递归
- 无后效性：未来与过去无关，一旦得到小问题的解，得到该解的过程不影响大问题的求解
- 两个元素
- 状态：求解过程进行到了哪一步，可以理解为一个子问题
- 转移：从一个状态(小问题)的解推导出另一个状态(大问题)的解的过程
二、例题
上述概念是比较标准的说法，但在实际做题中个人更倾向于另一种分析方式，下面以几个经典的题目来引入动态规划的求解
补充一点：解题时一定要记得初始化，这点很重要
1.[Daimayuan Online Judge.走楼梯]
题目描述
楼梯一共有 \(n\) 阶，上楼可以一步上一阶，也可以一步上二阶。
请求出走到第 \(n\) 阶共有多少种不同的走法。
输入格式
一行一个整数 \(n\)
输出格式
一行一个整数表示答案
输入样例
4
输出样例
5
数据规模
对于 \(100%\) 的数据，保证 \(1≤n≤50\)
解题思路
- 状态表示：\(f[i]\) 表示走到第 \(i\) 个台阶的方案，属性是方案数
- 状态计算：走到第 \(i\) 个台阶，所走的最后一步只有两种方式，从 \(i-1\) 阶台阶走一阶或者从 \(i-2\) 阶台阶走两阶，则 \(f[i] = f[i-1]+f[i-2]\)
C++代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 55;
typedef long long LL;
int n;
LL f[N];
int main() {
cin >> n;
f[0] = 1, f[1] = 1;
for (int i = 2; i <= n; i++) {
f[i] = f[i - 1] + f[i - 2];
}
cout << f[n] << endl;
return 0;
}
2.[Daimayuan Online Judge.最长上升子序列]
题目描述
给定一个长度为 \(n\) 的数组 \(a_1,a_2,…,a_n\)，问其中的最长上升子序列的长度。也就是说，我们要找到最大的 \(m\) 以及数组 \(p_1,p_2,…,p_m\)，满足 \(1≤p_1<p_2<⋯<p_m≤n_1≤p_1<p_2<⋯<p_m≤n\) 并且 \(a_{p_1}<a_{p_2}<⋯<a{p_m}\)
输入格式
第一行一个数字 \(n\)
接下来一行 \(n\) 个整数 \(a_1,a_2,…,a_n\)
输出格式
一个数，表示答案
输入样例
6
3 7 4 2 6 8
输出样例
4
数据范围
对于所有数据，保证 \(1≤n≤1000,1≤a_i≤10^9\)
解题思路
- 状态表示：\(f[i]\) 表示以 \(q[i]\) 为结尾的上升子序列，属性值是长度最大值
- 状态计算：初始化 \(f[i]=1\)，只考虑自身一个元素。考虑其前一个数是 \(q[j](1\le j<i)\)，如果 \(q[j]<q[i]\)，则 \(q[i]\) 可以接上，即 \(f[i]=max(f[i],f[j]+1)\)。最后对所有取最大值即为答案
该问题存在进阶，假设数据范围 \(1≤n≤100000\)，如何求解？
C++代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int q[N], f[N];
int n;
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &q[i]);
for(int i = 1; i <= n; i++)
f[i]=1;
int res=0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j < i; j++) {
if (q[i] > q[j])
f[i] = max(f[i], f[j] + 1);
res = max(res, f[i]);
}
}
cout << res;
return 0;
}
3.[Daimayuan Online Judge.最长公共子序列]
题目描述
给定一个长度为 \(n\) 的数组 \(a_1,a_2,…,a_n\) 以及一个长度为 \(m\) 的数组 \(b_1,b_2,…,b_m\)，问 \(a\) 和 \(b\) 的最长公共子序列的长度
也就是说，我们要找到最大的 \(k\) 以及数组 \(p_1,p_2,…,p_k\)，数组 \(l_1,l_2,…,l_k\) 满足 \(1≤p_1<p_2<⋯<p_k≤n\) 并且 \(1≤l_1<l_2<⋯<l_k≤m\) 并且对于所有的 \(i(1≤i≤k)\) ，\(a_{p_i}=b_{l_i}\)
输入格式
第一行两个整数 \(n,m\)
接下来一行 \(n\) 个整数，\(a_1,a_2,…,a_n\)
接下来一行 \(m\) 个整数，\(b_1,b_2,…,b_m\)
输出格式
输出一个整数，表示答案
输入样例
6 5
3 2 4 5 3 2
4 3 5 1 2
输出样例
3
数据范围
对于所有数据，保证 \(1≤n,m≤1000,1≤a_i,b_i≤10^3\)
解题思路
- 状态表示：\(f[i][j]\) 表示 \(a[1]\) 到 \(a[i]\) 与 \(b[1]\) 到 \(b[j]\) 的公共子序列，求长度最大值
- 状态计算：考虑 \(a[i]\) 和 \(b[j]\)，那么可分为 \(a[i]=b[j]\) 和 \(a[i]!=b[j]\) 两种情况
- \(a[i]!=b[j]\)：那么 \(a[i]\) 和 \(b[j]\) 可以舍弃一个，但是 \(a[i]\) 可能和 \(b[1]\) 到 \(b[j-1]\) 中的某个匹配或者 \(b[j]\) 可能和 \(a[1]\) 到 \(a[i-1]\) 中的某个匹配，故 \(f[i][j]=max(f[i-1][j],f[i][j-1])\)
- \(a[i]=b[j]\)：那么 \(f[i][j]=f[i-1][j-1]+1\)
C++代码
#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int n, m;
int x[N], y[N];
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> x[i];
for(int i = 1; i <= m; i++)
cin >> y[i];
f[0][1] = 0, f[1][0] = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if (x[i] == y[j])
f[i][j] = f[i - 1][j - 1] + 1;
else
f[i][j] = max(f[i][j - 1], f[i - 1][j]);
}
}
printf("%d\n", f[n][m]);
return 0;
}