动态规划入门-线性动态规划

ID: 372

客观题

尝试: 10

已通过: 7

难度: 3

上传者:

boya

标签>

教程

动态规划算法(DP,Dynamic Programming)是针对满足特定条件的一类问题，对各状态进行分阶段、有顺序、无重复、决策性的遍历求解。

动态规划把原问题视作若干个重叠子问题的逐层递进，每个子问题求解过程都构成一个“阶段”。在完成前一个阶段的计算后，动态规划才会执行下一阶段的计算。

为了保证这些计算能够按顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响，这就是“无后效性”。也就是，动态规划对状态空间的遍历构成一张有向无环图，遍历顺序就是该有向无环图的一个拓扑序。有向无环图中的节点对应问题的“状态”，图中的边则对应状态之间的“转移”，转移的选取就是动态规划中的“决策”。

很多情况下，动态规划用于求解最优化问题，下一个阶段的最有解应该能够由前面各阶段的最优解导出。这个条件被称为“最优子结构”。

“状态”、“阶段”、“决策”是构成动态规划算法的三要素，而“子问题重叠”“无后效性”和“最优子结构”是问题能用动态规划求解的三个基本条件。

子问题重叠：子问题与原问题结构相似，规模小些，计算步骤方法完全一样；原问题可以多次重复计算子问题得到。“子问题重叠”就意味着动态规划可以从小问题出发递推求解出大问题，也可以利用递归从大问题出发，递归求解小问题，直到边界，可以利用记忆化“空间换时间”的思想优化，这就是“记忆化搜索”。

最优子结构：大问题的最优解是由小问题的最优解得到的，小问题最优解可以推导大问题的最优解。

将当前阶段与前一个阶段用数学公式建立起联系，这个数学公式就是“状态转移方程”，转移可以是之前阶段对应的状态值推到当前阶段状态值，也可以是当前阶段状态值推到以后阶段对应的状态。

我们使用一道例题来学习动态规划的入门知识：

经典题目：数字三角形 Number Triangles

观察下面的数字金字塔。写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

        7 
      3   8 
    8   1   0 
  2   7   4   4 
4   5   2   6   5

在上面的样例中,从 7→3→8→7→5 的路径产生了最大。

【思路点拨】

首先，贪心做法“从上往下，始终选择当前最大的分支去走”是不对的，在选择的时候上面较小而选择走其他路径，而这条路径后面有一个或多个比较大的值，也就是贪心“鼠目寸光”。

暴力遍历每一条路径，时间复杂度为 $2^n$ ( $n$ 为数塔的高度)，会超时。参考代码如下：

#include<bits/stdc++.h>
using namespace std;
int r;int a[1001][1001];
int ans=-1;
void dfs(int i,int j,int sum){
	if(i==r+1)
	{
		ans=max(sum,ans);
		return;
	}
	dfs(i+1,j,sum+a[i][j]);
	dfs(i+1,j+1,sum+a[i][j]);
}
int main(){
	scanf("%d",&r);
	for(int i=1;i<=r;i++)
	   for(int j=1;j<=i;j++)
	      scanf("%d",&a[i][j]);
    dfs(1,1,0);    
    printf("%d",ans);
return 0;	
 }

暴力超时的原因就是，每次计算一个状态点的值，都需要递归到最后一层，这样曾经计算过得值就要重新计算一次，我们可以采用记忆化搜索，记录算过的状态值。

方法一：记忆化搜索，函数 $dfs(i,j)$ 返回值表示从 $(i,j)$ 出发到达最后一层路径数字和的最大值，那么 $dfs(i,j)= max(dfs(i+1,j),dfs(i+1,j+1))+a[i][j]$ , 可以利用数组记录 $dfs(i,j)$ 的值（因为下次调用的时候直接使用）。

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int a[N][N],f[N][N];
int r;
int dfs(int i,int j){
	if(f[i][j]!=-1)return f[i][j]; //如果算过了，就直接放回
	if(i==r)return f[i][j]=a[i][j]; //递归边界
	return f[i][j]=max(dfs(i+1,j),dfs(i+1,j+1))+a[i][j]; 
 } int main(){
	cin>>r;
	for(int i=1;i<=r;i++)
		for(int j=1;j<=i;j++)
			cin>>a[i][j];
	memset(f,-1,sizeof(f));//-1 表示状态未被计算过 
	cout<<dfs(1,1);
	return 0;
}

当然，也可以从最后一行往上递归，尝试写一写。

提示：方法二，记忆化搜索， $dfs(i,j)$ 表示从第 $(1,1)$ 走到 $(i,j)$ 路径上的数字和的最大值。 $dfs(i,j)=max(dfs(i-1,j-1),dfs(i-1,j))$

这个问题中，我们发现当前状态的最优值，是建立在前一个阶段几个“子问题”最优基础上的，这就是动态规划。动态规划是求类最优的问题的方法，利用问题可以划分成与原问题相似的子问题，将原问题视作若干个重叠子问题逐层递进，每个子问题的求解过程都构成一个“阶段”。在完成前一个阶段的计算后，动态规划才会执行下一阶段的计算。

为了保证这些计算能够按顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响，也就是“无后效性”。

动态规划对状态空间的遍历构成一张有向无环图，遍历顺序就是该有向无环图的一个拓扑序。有向无环图中节点对应问题中的“状态”，图中的边则对应状态之间的“转移”，转移的选取就是动态规划中的“决策”。

下一个阶段最优解应该能够由前面各阶段子问题的最优解导出，这个条件就是“最优子结构”。

“状态”“阶段”“决策”是构成动态规划算法的三要素，“子问题重叠性”“无后效性”“最优子结构性质”是问题能够用动态规划求解的三个基本条件，也是分析问题的切入口。

动态规划算法把相同的计算过程作用于各阶段同类子问题，状态之间的装换关系可以用一个数学方程表示，这就是“状态转移方程”。一般求解动态规划，分成这几个关键步骤：

（1）定义状态，就是求解问题抽象化描述。例如“数字三角形”中定义 $f[i][j]$ 表示从最底层走到 $(i,j)$ 路径上数字和的最大值。这一步尤为重要，定义的状态应该具备“子问题重叠性”、“无后效性”、“最优子结构”，状态定义混淆，往往是求解这类问题失败的原因。

（2）状态转移方程，就是用比较严谨的数学语言描述当前状态，与前一个阶段状态间的关系，也就是与子问题间的关系，往往选择一个最优的子问题进行转移。

（3）转移顺序，一般可以分成“顺推”和“逆推”。“顺推”就是从已知要位置一步一步递推，要求当前阶段全部求解完后，才能求下一个阶段，本质就是在拓扑序上顺序求解。在实际编程中，往往忽略转移顺序出现“当前要计算的值，需要用到前一个阶段的值，而前一个阶段的值都没有计算过”这种错误。很多问题阶段划分不是很明显，需要先进行拓扑排序。如果搞不清阶段间的前后顺序，可以“逆推”，也就是递归求解，状态对应的值需要记录，以方便后面重复使用提高效率，这就是记忆化优化，也就是计算化搜索。

(4)明确边界（起点的值）

(5)目标。

以“数字三角形”为例，我们进行分析：

方法三:动态规划-从下往上

（1）定义状态， $f[i][j]$ 表示从下往上走到 $(i,j)$ 路径上数字和的最大值。

（2）状态转移方程， $f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j]$

（3）转移顺序：本问题阶段划分很清晰，每一层就是一个阶段，层数 $i$ 的变化应该从大到小。

（4）边界：最下面一层 $f[n][j]=a[n][j]$ ，也就是起点。

（5）目标： $f[1][1]$

方法四：动态规划-从上往下

（1）定义状态， $f[i][j]$ 表示从上往下走到 $(i,j)$ 路径上数字和的最大值。

（2）状态转移方程， $f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j]$

（3）转移顺序，阶段划分清晰，层数 $i$ 应该从小到大。

（4）边界： $f[1][1]=a[1][1]$ ，目标 $max(f[n][1],f[n][2]...f[n][n])$

动态规划的艺术在于状态设计和问题与子问题之间的转移，如何把问题抽象成状态空间，进一步抽象成 $DP$ 的状态表示，往往考察选手的智力水平，通过大量练习可以提升这方面的能力。

经典模型

模型1：最长上升子序列 $LIS$

问题描述：给定一个长度为 $N$ 的数列 $A$ ，求数值单调递增的子序列的长度最长是多少。 $A$ 的任意子序列 $B$ 可表示为 $B=\{A_{k_1},A_{k_2},...,A_{k_p}\}$ ，其中 $k_1<k_2<...<k_p$ 。

定义状态： $F[i]$ 表示以 $A[i]$ 为结尾的“最长上升子序列”的长度

状态转移方程： $F[i]=max(F[j]+1)(0 \leq j<i,A[j]<A[i])$

转移顺序：阶段划分明显，从序列开始，从前到后边界： $F[1]=1$

目标： $ans=max\{F[i]\} (1\leq i \leq N)$

时间复杂度： $O(N^2)$

优化：转移过程实际是去前面找一个能接的最长子序列，然后接上，如果前面最长子序列用一个单调递增的数组维护，利用二分查找，可以 $O(\log{N})$ 找到第一个大于等于或第一个大于（求严格单调递增 $LIS$ ）的位置，如果这个位置没有超过序列的长度，那直接更新这处的值，否则新增递增序列的长度插入到末尾，这样递增序列的最长长度就是答案，复杂度为 $O(N\log{N})$ 。数据结构也可以进行优化。

模型2：最长公共子序列 $LCS$

问题描述：给定两个长度分别是 $N$ 和 $M$ 的字符串 $A$ 和 $B$ ，求既是 $A$ 的子序列又是 $B$ 的子序列的字符串长度最长是多少。

状态定义： $F[i][j]$ 表示前缀子串 $A[1\dots i]$ 与 $B[1 \dots j]$ 的“最长公共子序列”的长度。

状态转移方程：$F[i][j]=max\{ F[i-1][j] , F[i][j-1] , if(A[i]==B[j])F[i-1][j-1] \}$

转移顺序： $i$ 从小到大， $j$ 从小到大

边界： $F[i][0]=F[0][j]=0$

目标： $F[N][M]$

模型3： $DAG$ 上最长路和最短路

问题描述：给定一个 $DAG$ 图 ( $DAG$ ，也就是 Directed Acyclic Graph 有向无环图。),求图中最长路或最短路。

经典例题

例1：[NOIP1999 普及组] 导弹拦截

【思路点拨】

（1）一套拦截系统最多可以拦截多个导弹，就是求一个序列的最长不上升子序列，暴力 $O(N^2)$ 会超时，利用二分优化到 $O(n\log {n})$ （经典模型里有思路）。

（2）拦截所有导弹最少的拦截系统数量，可以贪心去求，用一个数组记录每一个系统拦截的最低高度，新来一个导弹，应该优先让能够拦截并且高度最低系统拦截（高度高的系统有能力拦截更高的），如果都无法拦截就新增加一套。复杂度是 $O(N^2)$ 。实际本问就是求最长上升子序列长度，那么二分优化 $LIS$ 就可以。

    内在原理是 Dilworth 定理：
    对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。
    对偶形式亦真：对于任意有限偏序集，其最长链中元素的数目必等于其最小反链划分中反链的数目 。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N];
int b[N];
int main()
{
	int t;
	while(scanf("%d",&t)!=EOF)a[++n]=t;
	
	int len=0;
	memset(b,0,sizeof(b));
	for(int i=1;i<=n;i++)
	{
		int pos=0;
		for(int j=30;j>=0;j--)
			if((pos+(1<<j))<=len && b[pos+(1<<j)]>=a[i])
				pos+=(1<<j);
				//b数组是下降序列，在下降序列里寻找第一个小于a[i]的位置 
		pos=pos+1;
		if(pos<=len)b[pos]=a[i];
		else b[++len]=a[i];
	}
	cout<<len<<endl;  
	
	int num=0;
	memset(b,0,sizeof(b));
	for(int i=1;i<=n;i++)
		{
			int pos=0;
			for(int j=30;j>=0;j--)
				if((pos+(1<<j))<=num && b[(pos+(1<<j))]<a[i])   
					pos+=(1<<j);
			pos++;   //b数组是上升序列，在上升序列里寻找第一个大于等于a[i]的位置 
			
			if(pos<=num)b[pos]=a[i];
			else b[++num]=a[i];
		}
	cout<<num;	
}

相似例题：木棍加工

偏序，按照 $L$ 从小到大排序，如果 $W$ 递减，就不需要停下来准备，也就是分成最少的几条 $W$ 下降的链，根据Dilworth 定理就等于最长的反链长度，也就是 $W$ 的严格上升子序列长度。

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10;
struct node
{
	int l,w;
}stick[N];
int n;
bool cmp(node a,node b)
{
	return a.l>b.l;
}
int ans[N],num;  //维护一个不下降序列 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>stick[i].l>>stick[i].w;
	//按照l从大到小排序 
	sort(stick+1,stick+n+1,cmp);
	//根据Dilworth定理，最少链的划分数目=最长反链的长度
	//也就是 求w中最长严格上升长度，转化为LIS
	 
	num=1;
	ans[1]=stick[1].w;
	
	for(int i=2;i<=n;i++)
	{
		int pos=lower_bound(ans+1,ans+num+1,stick[i].w)-ans;
		if(pos<=num)ans[pos]=stick[i].w;
		else ans[++num]=stick[i].w;
	}
	cout<<num;
	return 0;	
}

变形例题：P1439 【模板】最长公共子序列

$subtask1: n\leq 10^3$

可以使用 $LCS$ 普通模型完成，设 $F[i,j]$ 表示前缀子串 $A[1...i]$ 与 $B[1...j]$ 的“最长公共子序列”的长度，时间复杂度 $O(nm)$ 。

$subtask2: n\leq 10^5$

要巧用 $1\dots n$ 的排列这个限制信息，对于第一个排列 $A[i]$ ,可以再 $B[]$ 中找到其对应的位置 $P[i]$ ，即 $P[i]$ 表示 $A[i]$ 在 $B[]$ 中的位置，那么 $P[i]$ 中最长上升序列就是答案。

画出图来， $i$ 是递增的，如果 $P[i]$ 也递增，那么就不会交叉，不交叉的数量越多越好，这就是 $LIS$ .

例2：LCIS(最长公共上升子序列)

题意：对于两个数列 $A$ 和 $B$ ，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列。

$subtask1 : n \leq 500 ,m \leq 500$

【解析】： $F[i,j]$ 表示 $A[1...i]$ 与 $B[1...j]$ 可以构成的 以 $B_j$ 为结尾 的 $LCIS$ 的长度。

当 $A_i \ne B_j$ 时， $F[i,j]=F[i-1,j]$

当 $A_i = B_j$ 时， $F[i,j]=max_{ 0 \leq k <j,B_k < B_j } \{ F[i-1,k]\} +1$=$F[i,j]=max_{ 0 \leq k <j,B_k < A_i } \{ F[i-1,k]\} +1$

上面的转移过程可以用三重循环进行计算,时间复杂度为 $O(nm^2)$ 。

	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(a[i]==b[j])
			{
				for(int k=0;k<j;k++)
					if(b[k]<a[i])
						f[i][j]=max(f[i][j],f[i-1][k]+1);
			}
			else f[i][j]=f[i-1][j];

对于例题CF10D LCIS，求LCIS长度，还要输出一个LCIS方案. 参考代码：点击

$subtask2: n\leq 3000 ,m\leq 3000$

数据规模扩大，需要进行优化处理。

在第二层循环 j 从 1 增大到 m 时，第一层循环 i 是一个定值，这使得条件 $B_k <A_i$ 是固定的。因此，当变量 j 增加 1 时，k 的取值范围从 $0\leq k <j$ 变为 $0 \leq k < j+1$ ，即整数 j 可能会进入新的决策集合。

也就是我们只需要 O(1) 地检查条件 $B_j<A_i$ 是否满足，已经在决策集合中的数则一定不会被去除。

我们把满足 $0\leq k<j,B_k<A_i$ 的 k 构成的集合称为 $F[i,j]$ 进行状态转移时的决策集合，记为 $S(i,j)$ 。

$S(i,j+1)= \begin{cases}S(i,j), & if & B_j>=A_i \\S(i,j)\cup \{j\}, & if & B_j<A_i \end{cases}$

上面的转移只要两重循环就可以求解,最终目标为 $max(F[n,j]),1\leq j \leq m$ 。

	for(int i=1;i<=n;i++){
		//val表示决策集合S(i,j)中f[i-1][k]的最大值 
		int val=0;
		for(int j=1;j<=m;j++)
		{
			if(a[i]==b[j])f[i][j]=val+1;
			else f[i][j]=f[i-1][j];
			
			//j即将增大j+1,检查j能否进入新的决策集合 
			if(b[j]<a[i])val=max(val,f[i-1][j]); 
			
		}
	}

在实现状态转移方程时，要注意观察决策集合的范围随着状态的变化情况。

对于“决策集合中的元素只增不减”的情景，就可以像本题一样维护一个变量来记录决策集合的当前信息，避免重复扫描，把转移复杂度降低一个量级。

例3. P1280尼克的任务

题意简化 ：给定 $k$ 个任务，每个任务持续时间为 $[p_j,p_j+t-1]$ ，时刻 $i$ 如果有任务尼克可以选择一个任务，如果时刻 $i$ 没有任务，尼克可以空闲，询问尼克 $[1,n]$ 时间段内最长休息时间。 $1 \leq n,k \leq 10^4$

分析：可以将任务按照开始时刻分类(排序)，如果时刻 $i$ 没有任务那就休息，如果有任务那可以枚举此时刻开始的所有任务，保留最大值。

那么可以定义状态： $f_i$ 表示时间 $[i...n]$ 最大休息时间。

如果时刻 $i$ 没有任务： $f_i=f_{i+1}+1$
枚举时刻 $i$ 开始的所有任务 $j$ $(p_j==i)$ ，保留最优值： $f_i = max(f_{p_j+t_j})$

转移是时间序列上线性的，按时间从大到小，线性dp基本模型。初始 $f_i=0$ ; 结果 $ans=f_1$ 。

每个任务只会被枚举一次，时间复杂度为 $O(n+k)$ .

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+10;
int n,k,f[N];
vector<int>ed[N];  
//ed[网格 表示时间 i 开始的所有任务对应的结束时间 
//读入的时候，就按时间分类了 
 
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n>>k;
	for(int i=1;i<=k;i++)
	{
		int p,t;
		cin>>p>>t;
		ed[p].push_back(p+t);  //p开始，p+t-1结束 p+t就空闲了 
	} 
	
	for(int i=n;i;i--)   //f[i] 表示[i...n]时间最大 要倒着进行 
	{
		if(ed[i].size()==0)  //没有 i时刻开始的任务
			f[i]=f[i+1]+1; 
		else
		{
			for(int j:ed[i])  //j表示这项任务结束后下一个时刻 
				f[i]=max(f[i],f[j]); 
		}
	} 
	cout<<f[1];
	return 0;
}

例4. P1717钓鱼

题意简化：给定 $H$ 的小时， $n$ 个鱼塘，第 $i$ 个鱼塘从开始钓鱼,开始每 $5$ min 钓 $fi$ ，每过 $5$ min 钓鱼量减少 $d_i$ ，依次递减。从第 $i$ 个鱼塘走到第 $i+1$ 个鱼塘需要 $5*t_izhuangt第一个鱼塘，最后可以停在任意一个鱼塘。询问$ H$ 小时的能钓到最多的鱼。 $1 \leq H \leq 16, 2 \leq n \leq 25$

分析

题目中都是以 5min 作为最小计算单位时间计算的，那么把所有时间都转化为多少个 5min， $H \rightarrow 12*H$ ，最优性问题常见的解决思路，就是贪心（问题本身要符合全局最优”）、动态规划（问题能够定义成分阶段“最优子结构”的形式）。

解法1：贪心

本质上，就是除了路上花的时间外，把时间分配到能钓到鱼多的鱼塘。枚举最后停留的鱼塘 $i$ ，除去路上花的时间，每一个 5min,选择 $1-i$ 鱼塘的鱼量最多的鱼钓鱼，直到时间用完，或没有鱼了。 选择当前最多鱼塘，可以使用大根堆进行优化。

枚举鱼塘 $O(n)$ ，时间依次递减 $O(12h)$ ，每次选择最多的鱼的鱼塘（堆优化） $O(\log i)$ ，那么整体时间复杂度就是 $O(n \times 12h \times \log n )$ .

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,h,f[26],t[26],d[26];
int sol(int num)  //只钓前num个鱼塘的鱼，最后停在第num个鱼塘
//返回最多的鱼 
{
	int tim=h*12;
	int ret=0; 
	for(int i=1;i<num;i++)tim-=t[i];
	
	priority_queue<pair<int,int> >que;  //创建一个大根堆，以当前鱼量为关键字，同时保留递减量
	for(int i=1;i<=num;i++)
		que.push({f[i],d[i]});
		
	while(tim>0)  //每过1个5min都挑一个鱼最多的鱼塘钓，此时不考虑路上时间
	{
		int fish=que.top().first,dert=que.top().second; que.pop();
		if(fish<=0)break;   //没鱼了
		ret+=fish;
		que.push({fish-dert,dert});
		tim--;
	} 
	return ret;	
}
int main()
{
	cin>>n;
	cin>>h;
	for(int i=1;i<=n;i++)cin>>f[i];
	for(int i=1;i<=n;i++)cin>>d[i];
	for(int i=1;i<n;i++)cin>>t[i];
	int ans=0;
	for(int i=1;i<=n;i++)
		ans=max(ans,sol(i));  //只钓1-i内的鱼
	cout<<ans;
	return 0;
}

解法2：动态规划

前 $i$ 个鱼塘，考虑第 $i$ 个鱼塘给分配多少个 $5min$ ，可以调到最多的鱼，给前 $i$ 个鱼塘分配 $j$ 个 $5min$ , $i$ 是阶段， $j$ 看做“资源”（“资源规划使得最优”），本质上是“泛化”的背包问题。

那么定义状态： $dp[i][j]$ 前i个湖停留 $j$ 个 5分钟所能钓到最多的鱼的数量

给第 $i$ 个鱼塘分配 $k$ 个 5分钟, 第 $i$ 个鱼塘能钓到的鱼就是 $f_i+ (f_i-d_i)+...+(f_i-(k-1)*d_i)=\frac{(2*f_i-(k-1)*d_i)*k}{2}$,当然 $f_i-(k-1)*d_i>=0$ ,否则会钓到负数鱼数量，肯定就不对了。

即得到 $dp$ 转移方程：$dp[i][j]=max(dp[i-1][j-t_{i-1}-k]+k*(2*f_i-(k-1)*d_i)/2)，fi-(k-1)*di>=0$

$dp[i][j]$ 初始化为0，答案就是： $max(dp[i][j])$

时间复杂度： $O(n*12h*12h)$

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=26+1,H=17+1;
int n,h,f[N],d[N],t[N];
int dp[N][12*H];
int main()
{
	cin>>n>>h;
	for(int i=1;i<=n;i++)cin>>f[i];
	for(int i=1;i<=n;i++)cin>>d[i];
	for(int i=1;i< n;i++)cin>>t[i];
	
	memset(dp,-1,sizeof(dp));   //判断是否有不合法的情况 
	int ans=0;
	dp[0][0]=0; 
	for(int i=1;i<=n;i++)
	{
		for(int j=t[i-1];j<=12*h;j++)  //要能走到第i个鱼塘，避免j-t[i-1]是负数 
		{
			dp[i][j]=dp[i-1][j-t[i-1]];  //不钓鱼
			for(int k=1;k<=j-t[i-1];k++)  //钓 k个 5分钟的鱼 
				if( f[i]-(k-1)*d[i]>=0 && dp[i-1][j-t[i-1]-k]!=-1) //鱼够  且前面合法 
				{
					dp[i][j]=max(dp[i][j],dp[i-1][j-t[i-1]-k]+(2*f[i]-(k-1)*d[i])*k/2);
				} 
			ans=max(ans,dp[i][j]);
		}		
	}
	cout<<ans;
	return 0;
}

例5. P1541[NOIP2010 提高组]乌龟棋

例6. P1006[NOIP2008 提高组]传纸条

题意简化：给定一个 $n*m$ 二维数字网格，从起点 $(1,1)$ 向下、向右走到终点，再从终点走到起点(方向相反)，路径不相交，求经过路径上数字和的最大值。

分析：首先“贪心走一条路，再走另外一条路” 是错误的，因为：第一路可能最大，第二天路小，而有可能两条都比较大，但总和更大。

可以两条路一起从起点走到终点，那么定义： $f[x1][y1][x2][y2]$ 表示第一条走到 $(x1,y1)$ ,第二条路走到 $(x2,y2)$ 经过的数字和最大。发现状态有冗余，因为 $x1+y1=x2+y2$ ，那么可以优化掉一维状态

例7. P4677山区建小学

题意简化：给定 $n$ 个村庄的位置（线性），建 $m$ 所学校，求所有村到附近一所的距离和的最小值。

分析：如果只建 $1$ 所学校，根据中位数的性质，学校应该建在 $n$ 所学校中位数的位置; 如果建 $2$ 所学校，可以枚举断点 $i$ ， $[1,i]$ 和 $[i+1,n]$ 各建一所学校，各自建在中位数处，如果暴力求时间复杂度为 $O(N^2)$ ,可以利用“前缀和”优化,时间复杂度优化到 $O(N)$ ，例题“Boyacoding "P1006. 建学校”

当 $m>2$ 就需要利用动态规划求解。

定义 $f[i][j]$ 表示前 $i$ 个村庄建 $j$ 所学校总距离最小值

$f[i][j]=min\{f[k][j-1]+cost(k+1,i)\}$ ，其中 $cost(k+1,i)$ 表示第 $k+1$ 至 $i$ 建一所学校的最小花费。

时间复杂度为 $O(n^2m)$ .

例8. P6304[eJOI2018]山

例9.P1279 字串距离

例10. P2051 [AHOI2009] 中国象棋

例11. P1018 [NOIP2000 提高组] 乘积最大

例12. P2516 [HAOI2010] 最长公共子序列

课后练习

1. [ABC354F] Useless for LIS

提示： $l[i]$ 表示原序列中 $a_1...a_i$ 以 $a_i$ 结尾最长上升子序列长度， $r[i]$ 表示原序列 $a_i...a_n$ 以 $a_i$ 开头最长上升子序列长度，如果满足 $LIS==l[i]+r[i]-1$ , $a_i$ 就可以是 LIS 的一个元素，否则不在 LIS 中。

$l[i]$ 和 $r[i]$ 可以使用 二分优化 或 线段树优化 在 $O(n\log n)$ 的复杂度内求得。

2.ABC369F Gather Coins

思路：直接求会MLE,转化为 LIS.按 x 排序，求 y 的 LIS

学习完毕

{{ select(1) }}

#edu1002. 动态规划入门-线性动态规划

经典题目：数字三角形 Number Triangles

经典模型

模型1：最长上升子序列 $LIS$

模型2：最长公共子序列 $LCS$

模型3： $DAG$ 上最长路和最短路

经典例题

例1：[NOIP1999 普及组] 导弹拦截

相似例题：木棍加工

变形例题：P1439 【模板】最长公共子序列

例2：LCIS(最长公共上升子序列)

例3. P1280尼克的任务

例4. P1717钓鱼

例5. P1541[NOIP2010 提高组]乌龟棋

例6. P1006[NOIP2008 提高组]传纸条

例7. P4677山区建小学

例8. P6304[eJOI2018]山

例9.P1279 字串距离

例10. P2051 [AHOI2009] 中国象棋

例11. P1018 [NOIP2000 提高组] 乘积最大

例12. P2516 [HAOI2010] 最长公共子序列

课后练习

1. [ABC354F] Useless for LIS

2.ABC369F Gather Coins

学习完毕

状态

开发

支持

#edu1002. 动态规划入门-线性动态规划

动态规划入门-线性动态规划

经典题目：数字三角形 Number Triangles

经典模型

模型1：最长上升子序列 LISLISLIS

模型2：最长公共子序列 LCSLCSLCS

模型3：DAGDAGDAG 上最长路和最短路

经典例题

例1：[NOIP1999 普及组] 导弹拦截

相似例题：木棍加工

变形例题：P1439 【模板】最长公共子序列

例2：LCIS(最长公共上升子序列)

例3. P1280尼克的任务

例4. P1717钓鱼

例5. P1541[NOIP2010 提高组]乌龟棋

例6. P1006[NOIP2008 提高组]传纸条

例7. P4677山区建小学

例8. P6304[eJOI2018]山

例9.P1279 字串距离

例10. P2051 [AHOI2009] 中国象棋

例11. P1018 [NOIP2000 提高组] 乘积最大

例12. P2516 [HAOI2010] 最长公共子序列

课后练习

1. [ABC354F] Useless for LIS

2.ABC369F Gather Coins

学习完毕

状态

开发

支持

还没有账户？

登录

模型1：最长上升子序列 $LIS$

模型2：最长公共子序列 $LCS$

模型3： $DAG$ 上最长路和最短路