#edu1001. 搜索-2

搜索-2

一、迭代加深

在状态空间中搜索，会遇到这种情况，“搜索树深度很深宽度很宽”。如果直接 DFS，深度很深（甚至无限），会递归层数太多，从而 TLE/MLE；如果直接 BFS，由于搜索树宽度很宽（甚至无限），队列空间爆炸。

而这种问题本质上来看，起点到目标点之间的距离并不遥远，可以用下图描述：

状态空间宽度和深度很大，不能直接使用 DFS 和 BFS ，可以结合 BFS,控制 DFS 递归深度，即迭代加深搜索（Iterative Deepening DFS,IDDFS）。

基本操作步骤如下：

  1. 设定搜索深度为 1，用 DFS 搜索到第 1 层即停止。也就是只搜深度为 1 的搜索树。
  2. 如果没有找到答案，再设定深度为 2，从起点开始重新搜索。
  3. 如果没找到答案，再将深度设定扩大 1。逐步扩大DFS搜索的深度，直到找到答案。

这个迭代过程，在每一层的广度上采用了 BFS 搜索的思想，搜索时采用 DFS ，节省空间。即控制深索的搜索深度，避免在某一个分支搜索的太深。

核心框架代码：

int dep;
void dfs(int p, ...)  //p代表递归深度
{
	if(p>dep)return;  //当深度超了，直接return
	...
	dfs(p+1,...)    //递归下一层，深度+1
}
//主函数中控制递归深度
int main()
{
	for(dep=2;;dep++)    //dep是全局变量
		{
			flag=0;
			dfs(1，...);  //参数中 1 表示递归深度
			if(flag)
			{
				//ans-print输出答案
				break;
			}
		}
}

1.例题：P1763 埃及分数

本题只能用搜索，搜索树如下图。每一层的元素是分子为 1、分母递增的分数；从上往下的一个分支，就是一个这个分支上所有的分数相加的组合；找到合适的组合就退出。

搜索树深度和宽度极大

搜索树深度和宽度极大。直接用 BFS,由于宽度太大，用不了几层，就会 MLE；直接用 DFS,递归深度太深，会 MLE/TLE。这种情况下使用迭代加深，控制 DFS 搜索深度，使得 DFS,搜索深度逐渐增大，直到找到答案，结合了 BFS 和 DFS 的优点。

本题参考代码：

#include<bits/stdc++.h>
using namespace std;

long long t[510],dep,flag;
long long ans[510];
bool check()
{
	if(ans[dep]==0||t[dep]<ans[dep])return true;
	return false;
}
long long gcd(long long a,long long b)
{
	if(b==0)return a;
	return gcd(b,a%b);
}
void dfs(int p,long long la,long long lb)
{
	if(p==dep)
	{
		if(lb%la==0)
		{
			t[p]=lb/la;
			if(check())
				memcpy(ans,t,sizeof(t));
			flag=1;
		}
		return;
	}
	for(long long  i=max((long long)t[p-1]+1,lb/la+1);la*i<lb*(dep-p+1);i++)
	{
		t[p]=i;
		long long nb=(long long)lb*i;
		long long na=(long long)la*i-lb;
		long long g=gcd(nb,na);
		dfs(p+1,na/g,nb/g);
	}
}
int main()
{
	int a,b;
	cin>>a>>b;
	for(dep=2;;dep++)
	{
		flag=0;
		dfs(1,a,b);
		if(flag)
		{
			for(int i=1;i<=dep;i++)
				printf("%d ",ans[i]);
			break;
		}
	}
	return 0;
}

update1:2024.4

由于题目新出了 Hack 数据，Hack 数据输入：570 877，会出现 TLE 的情况，所以需要更新一把题解。看了一眼之前的题解，写的不够详细，也重新增加一些细节。

优化1：新一层分母 ii 下限

比前一个分母大 i>t[p−1]i>t[p-1]，由于不是最后一层 有 lalb>1i\frac{la}{lb}>\frac{1}{i},得到 i>lblai>\frac{lb}{la}，综上 max(t[p−1],lbla)+1≤imax(t[p-1],\frac{lb}{la})+1 \leq i .

优化2：新一层分母 ii 上限

总共 depdep 层，当前是 第 pp 层，那么如果从第 pp 到 depdep 层，每层分母取 ii ,剩下 dep−p+1dep-p+1 层分数总和最大，要超过 lalb\frac{la}{lb}，可得到如下式子：

lalb<(dep−p+1)∗1i\frac{la}{lb}<(dep-p+1)* \frac{1}{i}

可得 ii 的上限:i<(dep−p+1)∗lblai<\frac {(dep-p+1)*lb}{la}

优化3：讨论最后两层，减少枚举次数 ---为了通过进一步优化

题目中要求最小分数 1107\frac{1}{10^7}，那么最后一个分母不能大于 10710^7 ，单纯约束，剪枝有限。由于是迭代加深, 深度越深，分母越大，随着深度加深，分母上限逐渐扩大，那么设置 分母上限为 limlim，从 10310^3 逐层扩大到 10710^7，每次深度加深，扩大 1010 倍，即 lim=lim∗10lim=lim*10

为了进一步剪枝优化，推导最后两层取值情况。

当只剩下两层时，即 p=dep−1p=dep-1 时 ，设最后两个分母为 x,yx,y，可得：

lalb=1x+1y\frac{la}{lb}=\frac{1}{x}+\frac{1}{y},即lalb=x+yxy\frac{la}{lb}=\frac{x+y}{xy}.

那么设 la∗z=x+y,lb∗z=x∗y{la*z=x+y},lb*z=x*y

可得一元二次方程：x2−(la∗z)∗x+(lb∗z)=0x^2-(la*z)*x+(lb*z)=0

当 Δ=(la∗z)2−4∗lb∗z>0\Delta =(la*z)^2-4*lb*z>0 时，存在两个不同的根，即 la2∗z−4∗lb>0,4∗lbla2<zla^2*z-4*lb>0,\frac{4*lb}{la^2}<z .(此处为 zz 的下界)

此时：$x=\frac{la*z-\sqrt{\Delta}}{2},y=\frac{la*z+\sqrt{\Delta}}{2}$

必须满足 2∣la∗z−Δ2 | la*z-\sqrt{\Delta} , 2∣la∗z−Δ2 | la*z-\sqrt{\Delta}

由于有 limlim 的限制，可以计算出 zz 的下界，进一步优化。

由于 x≤lim,y≤lim,x<yx \leq lim, y \leq lim,x<y :

la∗z=x+y<2∗limla*z=x+y < 2*lim，可得 z<2∗limlaz<\frac{2*lim}{la}

lb∗z=x∗y<lim2lb*z=x*y<lim^2，可得 z<lim2lbz<\frac{lim^2}{lb}

即 z<min(2∗limla,lim2lb)z<min(\frac{2*lim}{la},\frac{lim^2}{lb})

综上 $\frac{4*lb}{la^2}<z<min(\frac{2*lim}{la},\frac{lim^2}{lb})$

加上优化 3 后，代码更新如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
long long t[510],dep,flag;
long long ans[510];
long long lim; 
bool check()
{
	if(ans[dep]==0||t[dep]<ans[dep])return true;
	return false;
}
long long gcd(long long a,long long b)
{
	if(b==0)return a;
	return gcd(b,a%b);
}
void dfs(int p,long long la,long long lb)
{
	if(p==dep)  //最后一层 
	{
		if(lb%la==0)
		{
			t[p]=lb/la;
			if(check())
				memcpy(ans,t,sizeof(t));
			flag=1;
		}
		return;
	}
	if(p==dep-1)  //最后两层  第三重优化 
	{
		int l=4*lb/(la*la)+1,r=min(2*lim/la,lim*lim/lb);   //进一步约束上下界 
		for(ll z=l;z<=r;z++)
		{
			ll dert=(la*z)*(la*z)-4*lb*z;
			ll s=sqrt(dert);
			if(s*s!=dert || ((la*z-s)&1) || ((la*z+s)&1) )continue;
			
			ll x=(la*z-s)/2,y=(la*z+s)/2;
			t[p]=x,t[p+1]=y;
			
			if(ans[p+1]==0 || ans[p+1]> t[p+1])
			{
				memcpy(ans,t,sizeof(t));
				flag=true; 
				return;
			}				
		} 
		return ;
	} 
	for(long long  i=max((long long)t[p-1]+1,lb/la+1);la*i<lb*(dep-p+1);i++)
	{
		t[p]=i;
		long long nb=(long long)lb*i;
		long long na=(long long)la*i-lb;
		long long g=gcd(nb,na);
		dfs(p+1,na/g,nb/g);
	}
}
int main()
{
	int a,b;
	cin>>a>>b;
	lim=1000;  //分母的上线 
	for(dep=2;;dep++)
	{
		flag=0;
		lim=1000;    //第三重优化，控制枚举分母上限 
		while(lim<=1e7&&flag==0)
		{
			dfs(1,a,b);
			lim=lim*10; 
		}
		
		if(flag)
		{
			for(int i=1;i<=dep;i++)
				printf("%d ",ans[i]);
			break;
		}
	}
	return 0;
}

2.例题：poj2248 Addition Chain

搜索框架：依次搜索序列中的每个位置 kk ,枚举 ii 和 jj 作为分支，把 x[i]x[i] 和 x[j]x[j] 的和填到 x[k]x[k] 上，然后递归下一个位置。

优化减枝：

1.优化搜索顺序

为了让序列中的数尽快逼近到n，在枚举i和j时从大到小枚举；

2.排除等效冗余

对于不同的 ii 和 jj，x[i]+x[j]x[i]+x[j] 可能是相等的。我们可以再枚举时用一个 bool 数组对 x[i]+x[j]x[i]+x[j] 进行判重，避免重复搜索每一个和。

经过观察分析可以发现，mm 的值(序列的长度)不会太长 (≤10)(\leq 10),而每次枚举每个数的和，分支很多，因此我们可以采用迭代加深搜索，从 1 开始限制搜索深度，若搜索失败就增加搜索深度重新搜索，直到找到一组解即可输出答案。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=10005;
int ans[N];
int n,m;
int dep; //迭代加深，深度限制 
bool flag;
void dfs(int step)
{
	if(step==dep+1)
	{
		if(ans[dep]==n)flag=1;
		return ;	
	}
	for(int i=step-1;i;i--)   //优化搜索顺序，从大到小 
	{
		ans[step]=ans[step-1]+ans[i];
		
		long long temp=ans[step];
		for(int j=step+1;j<=dep;j++)temp*=2;//可行性剪枝 
		if(temp<n)return;
		dfs(step+1);
		if(flag)return ;
	}
}
int main()
{
	
	while(scanf("%d",&n),n)
	{
		if(n==1)
		{
			cout<<1<<endl;
			continue;
		}
		ans[1]=1;
		flag=0;
		for(dep=2;dep<=n;dep++)
		{
			m=dep;
			dfs(2);
			if(flag)
			{
				for(int i=1;i<m;i++)
					cout<<ans[i]<<" ";
				cout<<ans[m];
				cout<<endl;
				break;
			}
		}
	}
}

二、BFS拓展

1. 双向 BFS

“起点”扩展一层，“终点”扩展一次，直到交汇，扩展节点数减少。

2. BFS+双端队列

又叫 "01BFS"，适合于边权只有 0 和1 的情况。详细可以参考另一篇博客“01BFS”

3. BFS+优先队列

这种算法核心思想是“贪心”，普通BFS,存入队列中待访问的节点，没有优先级，依次访问，但有的时候这些等待的节点按照某种贪心策略，具有优先级，按照优先级出队，能够最早到达目标节点，那么只需要将具有“缓存”功能的普通队列变为按优先级排序的“优先队列”(STL中priority_queue),例如"Dijkstra算法".

例题1. 正边权最短路 P4779 【模板】单源最短路径（标准版）

例题2.[ABC214C] Distribution

4. BFS+一个节点多次进队

例题1：[ABC348D] Medicines on Grid

本题用“优先队列一个点只走一次”，是错误的，因为走短的路可能吃到值很大的药。

例题2：带负边权最短路

三、启发式搜索

例题： 整理盘子

**解法一：BFS+启发函数，也就是所谓的'A*' **

nn个 盘子的状态很多 O(n!)O(n!)，直接盲目BFSBFS 会 MLE/TLE，当然通过剪枝，可能通过 n≤10n \leq 10 的 subtask。

设计启发函数，启发函数=从起点到当前点的代价（实际）+ 当前点到目标点的估计代价，注意：估计代价需要小于等于当前点到目标点的实际代价，否则第一次搜到目标点，可能花费更高。

nn 个盘子离散化后，为了更好存储 n 个盘子的状态，可以将 nn 个盘子转化为字符串，本质与状压思想类似。本题设计启发函数是关键，从小到大排，如果相邻两个盘子编号相差不是 11，那为了有序，至少需要翻转一次，最终目标是升序列，可以让 a[n+1]=n+1a[n+1]=n+1。

将n个盘子的状态，与对应的启发函数打包放入优先队列（小根队），以启发函数值为关键字，优先搜索启发函数小的状态点，当第一次搜到目标点时，就是最少操作次数。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int ,string> pii;
int n,a[55],b[55];
struct node{
	int step,val;
	string s;
};
bool operator <(node x,node y)
{
	return x.val>y.val;
}
int cal(string s)    //计算当前状态到目标状态最小的反转次数，必须严格小于实际反转次数 
{
	s+=char(n+'A');   //第n+1位置上放n+1对应的字符，保证从小到大 
	int ret=0;
	for(int i=1;i<=n;i++)
		if(abs(s[i]-s[i+1])!=1)
			ret++;
	return ret;
}

int bfs(string s)
{
	int h=cal(s);
	if(h==0)return 0; 
	priority_queue<node>que;
	que.push({0,h,s});
	
	while(que.size())
	{
		int step=que.top().step;
		string x=que.top().s;
		que.pop();
		for(int i=1;i<=n;i++)
		{
			string y=x;
			reverse(y.begin()+1,y.begin()+i+1);
			int h=cal(y);    //h为估价函数 
			if(h==0)return step+1;
			que.push({step+1,step+1+h,y});  //小根堆，键值为走到当前状态的步数+估价函数值 
		}
	}
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
	sort(b+1,b+n+1);
	string s=" ";
	for(int i=1;i<=n;i++)
	{
		a[i]=lower_bound(b+1,b+n+1,a[i])-b;
		s+=char('A'+a[i]-1);
	}
	cout<<bfs(s);
	return 0;
}

**解法二：迭代加深+启发函数，也就是 IDA* **

由于 dfs 递归深度太深，会出现 MLE/TLE，而实际上起点到目标点距离并不会特别长，如果不控制递归深度，从某棵子树递归下去，将会爆炸。

那么可以控制递归深度，当递归深度超过限定后，提前返回，这就是迭代加深，通过迭代加深和剪枝可以拿到部分分，本质上还是 bfs。

盲目 dfs 是超时的根本原因，通过启发函数值，如果启发函数值超过限定递归深度，那就提前返回，这种剪枝能有效减少无用搜索，这就是IDA* 原理。

估价函数设计如下：

int h()
{
	int ret=0;
	for(int i=1;i<=n;i++)
		if(abs(a[i]-a[i+1])!=1)ret++;
	return ret;
}

完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int ,string> pii;
int n,a[55],b[55];
bool flag;
int h()
{
	int ret=0;
	for(int i=1;i<=n;i++)
		if(abs(a[i]-a[i+1])!=1)ret++;
	return ret;
}
void dfs(int g,int f,int pre)
{
	if(flag || g+h()>f)return;  //估计步数超了规定深度，提前退出 
	if(h()==0)  //找到目标状态 
	{
		flag=true;
		return;
	}
	for(int i=1;i<=n;i++)
		if(i!=pre)  //保证翻转长度与上次不同
		{
			reverse(a+1,a+i+1);  //翻转 
			dfs(g+1,f,i);
			reverse(a+1,a+i+1);  //回溯还原 
		} 
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
	sort(b+1,b+n+1);
	string s=" ";
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(b+1,b+n+1,a[i])-b;  //离散化
	a[n+1]=n+1;
	
	for(int dep=0;;++dep)  //迭代加深 
	{
		flag=false;
		dfs(0,dep,0);
		if(flag)
		{
			cout<<dep;
			return 0;
		}
	} 
	
	return 0;
}

四、折半搜索

除了迭代加深控制搜索深度之外，双向搜索也可以避免在深层子树上浪费时间。

一些题目中，给定了“起点”，也给定了“终点”，搜索的状态空间会与层度呈现指数级增长，如果单纯从“起点” DFS 或 BFS,就会 TLE/MLE。

在这种情况下，就可以采用双向搜索，从起点和终点出发各搜索一般状态，产生两颗深度减半的搜索树，在中间交会、组合成最终的答案。

这种情况下，采用 BFS,就是双向 BFS，从起点、终点分别开始，两边轮流进行，每次各扩展一整层（初始时起点、终点入队）。 为了方便理解，可以把从起点扩展的点都标记为白色，终点扩展的标记为黑色，当从白点往外扩展遇到黑点，说明搜索相遇了，反之亦然。

有的时候，DFS 搜索深度固定，但状态数随着深度呈指数增长。可以采用双向 BFS 思想，控制 DFS 搜索深度，先搜深度一半的状态，标记到一半的状态点，再搜索另一半深度，终点状态如何与之前标记过的正好匹配，就说明是符合条件的一种，这就是折半搜索，“meet in the middle”。

1.例题：Anya and Cubes

题目大意：得定 n(n≤26)n(n\leq 26) 个数，可以将其中任意 kk 个数转变为阶乘，求:选出任意个数使他们和的等于 SS 的方案数。

分析：对于任意一个数，有三种可能：不选、选、选了并转变为阶乘，这样直接 DFS,时间复杂度为 O(326)O(3^{26}),会爆炸。

可以控制先 DFS 一般深度，记录所有出现的结果，再搜索另外一半，复杂度为 O(313+313)O(3^{13}+3^{13})。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k,a[27];
ll S,ans,jie[20]={1};
map<long long ,long long >num[27];  //num[k][i] 表示前一半  选了k个阶乘 总和为i 的方案数
void dfs1(int p,int j,ll sum)   //搜到第p个位置，之前阶乘用了j次，之前总和为sum 
{
	if(j>k||sum>S)return;
	if(p==n/2+1)  //搜完前一半 
	{
		num[j][sum]++;return;
	}
	dfs1(p+1,j,sum);  //a[p]不选
	dfs1(p+1,j,sum+a[p]) ; //选a[p]
	if(a[p]<20)  //不会溢出long long
		dfs1(p+1,j+1,sum+jie[a[p]]); 
}
void dfs2(int p,int j,ll sum)  //从n/2+1开始搜索 搜到第p个数 之前用了j个阶乘 总和为sum 
{
	if(j>k||sum>S)return;
	if(p==n+1)   //搜索完另外一半 
	{
		for(int i=0;i<=k-j;i++)  //前一半用0...k-j次阶乘 
			if(num[i].count(S-sum))//如果直接使用 num[i][S-sum]>0 会插入大量无用状态到map中，浪费时间 
				ans+=num[i][S-sum];
		return; 
	}
	dfs2(p+1,j,sum);
	dfs2(p+1,j,sum+a[p]);
	if(a[p]<20)
		dfs2(p+1,j+1,sum+jie[a[p]]); 
}
int main()
{
	cin>>n>>k>>S;
	for(int i=1;i<=n;i++)cin>>a[i]; 
	for(int i=1;i<=19;i++)jie[i]=jie[i-1]*i;//20!都会溢出longlong，也必然大于S
	
	dfs1(1,0,0);
	dfs2(n/2+1,0,0);
	
	cout<<ans;
	return 0;
}

2.P4799 世界冰球锦标赛

题意：

Bobek 有 MM 元钱，共有 NN 场比赛，每场比赛的门票都有一个价格 CiC_i 。 问在总票价不超过 MM 元钱的情况下，Bobek 共有多少种不同的观赛方案。

注1：若方案 1 中观看了某场比赛，方案 2 中未观看该场，则认为两种方案不同

注2： $1\leq N \leq 40 ,1 \leq M \leq 10^{18},C_i \leq 10^{16}$

分析： 学过背包的同学，可能会想到背包模型，f[i][s]f[i][s] 表示前 ii 场比赛花了 ss 元的方案数，但看到数据范围，这种方法显然不行。

比赛场数少，对于每场比赛要么观看、要么不管看，直接 DFSDFS ,时间复杂度 O(240)O(2^{40})，炸了。优化一下，折半搜索，O(220+220)O(2^{20}+2^{20})。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll m,a[41],ans; 
vector<ll>s; 
void dfs1(int p,ll sum)//搜到第p个数,之前总和为sum 
{
	if(sum>m)return;
	if(p==n/2+1)
	{
		s.push_back(sum);
		return;
	}
	dfs1(p+1,sum);
	dfs1(p+1,sum+a[p]);
} 
void dfs2(int p,ll sum)
{
	if(sum>m)return;
	if(p==n+1)
	{
		ll num=upper_bound(s.begin(),s.end(),m-sum)-s.begin();
		ans+=num;
		return;
	}
	dfs2(p+1,sum);
	dfs2(p+1,sum+a[p]);
} 
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i]; 
	dfs1(1,0);
	sort(s.begin(),s.end());
	dfs2(n/2+1,0);
	cout<<ans;


	return 0;
}

五、记忆化搜索

很多问题需要计算状态对应的值（或最优值），但是状态前后顺序不好确定（状态拓扑序不清楚），也就是不好直接递推（从已知递推到未知）求解，此时往往递归求解（从位置递归求解到已知）。

例如经典问题斐波那契数列，如果直接用递归求解，代码如下：

#include<bits/stdc++.h>
using namespace std;
long long f(int i)
{
	if(i==1||i==2)return 1;
	return f(i-1)+f(i-2);
}
int main()
{
	int n;
	cin>>n;
	cout<<f(n);
	return 0;
}

当输入 50，递归就会超时。 超时原因就是每次都递归到边界才返回，重复计算了大量状态值，当然可以利用多种方法求解 T(n)=T(n−1)+T(n−2)T(n)=T(n-1)+T(n-2) 对应的时间复杂度，是一个指数函数。

优化的方法就是“记忆化”，算过的状态通过数组记录下来，下次用到直接返回，也就是典型的“用空间换时间”的思想。

#include<bits/stdc++.h>
using namespace std;
long long t[91];   //t数组记录对应状态的值 
long long f(int i)
{
	if(t[i]!=0) return t[i];  //t[i]!=0 表示状态i的值已经算过，直接返回 
	if(i==1||i==2)return t[i]=1;   
	return t[i]=f(i-1)+f(i-2);  //返回的同时记录状态对应的值 
}
int main()
{
	int n;
	cin>>n;
	cout<<f(n);
	return 0;
}

1.P7074[CSP-J2020]方格取数

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
const long long int INF=1e11;
int a[N][N];
long long f[N][N][3];
int n,m;
long long dfs(int i,int j,int tag)
{
	if(i==1&&j==1)return a[1][1];
	if(i<1||i>n||j>m||j<1)return -INF;
	if(f[i][j][tag]!=-INF)return f[i][j][tag];
	if(tag==0) 
		return f[i][j][tag]=max(max(dfs(i,j-1,0),dfs(i,j-1,1)),dfs(i,j-1,2))+a[i][j];
	if(tag==1)
		return f[i][j][tag]=max(dfs(i-1,j,0),dfs(i-1,j,1))+a[i][j];
	if(tag==2)
		return f[i][j][tag]=max(dfs(i+1,j,0),dfs(i+1,j,2))+a[i][j];
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			f[i][j][0]=f[i][j][1]=f[i][j][2]=-INF;
	
	cout<<max(dfs(n,m,0),dfs(n,m,1));
	return 0;
	
}

数字三角形 Number Triangles

请用递推递归 4 种方法完成本题。

记忆化搜索的本质是动态规划，当状态间的拓扑不清楚，如果用递推，就需要先找到正确的拓扑序，采用递归，从未知逐次询问上一阶段，直到递归到边界（已知），可以避免求拓扑序，利用记忆化，避免状态重复计算。

01背包问题：从爆搜到记忆化，到递推

P1048 [NOIP2005 普及组] 采药

MM种药，TT的采药总时间，第ii种药采用时间为viv_i，药的价值为wiw_i,询问采药时间不超过TT，能采到最大价值的药是多少？

  1. 暴力搜索，第ii种药采或不采，时间复杂度为O(2M)O(2^M)

  2. 记忆化搜索

    dfs(i,j)dfs(i,j)表示前ii种药总时间不超过jj的情况下，能采到最大价值的药 dfs(i,j)=max(dfs(i−1,j),dfs(i−1,j−v[i])+w[i])dfs(i,j)=max(dfs(i-1,j),dfs(i-1,j-v[i])+w[i])

  3. 递推 f[i][j]=max(f[i−1][j],f[i−1][j−v[i]]+w[i])f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])

    空间优化：0/1滚动数组优化和自我滚动

学习完毕

{{ select(1) }}

  • YES
  • NO
  1. 关于
  2. 联系我们
  3. Language
  4. 兼容模式
  5. 主题
  3. Worker 0 in 62ms
  4. Powered by Hydro v4.13.3 Modified by byx QQ465039728
  5. 陕ICP备2023000766号