线性DP
ZhuRanCheng · · 个人记录
线性动态规划
一、基本概念
动态规划是一种解决多阶段决策问题的优化方法,把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解。
二、动态规划适用范围
能采用动态规划求解的问题的一般要具有3个性质:
1.最优性原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优性原理。 2.无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。 3.有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)。
三、动态规划三要素
动态规划有三要素:阶段、状态和决策
阶段:把—个问题的过程,恰当地分为若千个相互联系的阶段,以便于按一定的次序去求解。描述阶段的变量称为阶段变量。
划分:一般是根据时间和空间的自然特征来进行的,但要便于问题转化为多阶段决策
状态:表示每个阶段开始所处的自然状况或客观条件。通常一个阶段有若干个状态(也可能只有一个状态),描述过程状态的变量称划分。
决策:表示当过程处于某一阶段的某个状态时,可以作出不同的决定,从而确定下一阶段的状态,这种决定称为决策。
四、动态规划一般流程
划分阶段->正确选择状态变量->确定状态转移方程。
五、例题
最长上升子序列
题目
题目描述
一个数的序列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)。
你的任务，就是对于给定的序列，求出最长上升子序列的长度。
输入格式
输入的第一行是序列的长度N(1≤N≤1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。
输出格式
最长上升子序列的长度。
分析
状态
dp数组为以i结尾的最长上升子序列的长度；
转移
先看样例
A: 1 7 3 5 9 4 8定义一个dp数组，表示以i结尾的最长上升子序列的长度。
则：dp[2] = max(dp[j]) + 1 在(a[j] < a[2]）时。
可得出状态转移方程:
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, a[1005], dp[1005], maxn = 1;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; i++)
dp[i] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (a[j] < a[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
maxn = max(maxn, dp[i]);
}
printf("%d", maxn);
return 0;
}