记忆化搜索算法

全栈程序员站长

发布于 2022-09-17 10:38:48

4050

发布于 2022-09-17 10:38:48

文章被收录于专栏：全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

概述

记忆化搜索算法事实上是一种对递归算法的优化 因为在递归算法中有很多重复计算，导致了非常离谱的时间和空间复杂度 所以我们采用记住计算结果的方式，能很大程度上减少复杂度

算法核心结构

此算法可以被抽象成为以下的结构：

f（problem p）{ 
   
    if(p has been solved){ 
   
         return the result
    }else{ 
   
         divide the p into some sub-problems (p1, p2, p3...)
         f(p1);
         f(p2);
         f(p3);
         ...
    }

例题1 AcWing 901. 滑雪

十分典型的记忆化搜索题目，主要体现在if(f[x][y]!=-1) return f[x][y];上。

#include<iostream>
#include<cstring>
using namespace std;

const int N=304;

int r,c;
int f[N][N];
int g[N][N];
int dx[]={ 
   0,-1,0,1},dy[]={ 
   -1,0,1,0};

int dp(int x,int y)
{ 
   
	if(f[x][y]!=-1) return f[x][y];
	
	f[x][y]=1;
	for(int i=0;i<4;i++)
	{ 
   
		int xi=x+dx[i],yi=y+dy[i];
		if(xi>=1&&xi<=r&&yi>=1&&yi<=c&&g[xi][yi]<g[x][y])
			f[x][y]=max(f[x][y],dp(xi,yi)+1);
	}
	
	return f[x][y];
}

int main()
{ 
   
	cin>>r>>c;
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++)
			cin>>g[i][j];
	
	memset(f,-1,sizeof(f));
	
	int res=0;
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++)
			res=max(res,dp(i,j));
		
	cout<<res;
	return 0;
}

例题2 AcWing 2067. 走方格

第十一届蓝桥杯省赛原题，除了记忆化搜索方法，还有正常dp方法可供选择。

#include<iostream>
using namespace std;

const int N=32;
int n,m;
int f[N][N];

int dfs(int x,int y)
{ 
   
	if(x&1||y&1)
	{ 
   
		if(f[x][y]) return f[x][y];
		if(x<n) f[x][y]+=dfs(x+1,y);
		if(y<m) f[x][y]+=dfs(x,y+1);
	}
	return f[x][y];
}

int main()
{ 
   
	cin>>n>>m;
	f[n][m] = n & 1 || m & 1;//判断nm是否同为偶数
	cout<<dfs(1,1);
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/164443.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

java