记忆化搜索算法

记忆化搜索算法概述记忆化搜索算法事实上是一种对递归算法的优化因为在递归算法中有很多重复计算,导致了非常离谱的时间和空间复杂度所以我们采用记住计算结果的方式,能很大程度上减少复杂度例题1AcWing901.滑雪例题2AcWing2067.走方格…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

概述

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

算法核心结构

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

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);
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164443.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 怎么完全卸载赛门铁克_赛门铁克专用卸载工具[通俗易懂]

    怎么完全卸载赛门铁克_赛门铁克专用卸载工具[通俗易懂]安装卸载是两个操作,完全相反,通常安装会比卸载简单,赛门铁克专用卸载工具是一款专门用于卸载赛门铁克系列软件的应用工具,赛门铁克专用卸载工具完美解决赛门铁克怎么卸载的难题,需要的用户可以下载!赛门铁克官方卸载工具相关说明:包括SymantecAntiVirus即SAV系列,SymantecClientSecurity即SCS系列,以及SymantecEndpointProtection即S…

  • Android 实现锚点定位

    Android 实现锚点定位

  • 卸载 x 雷某度!GitHub 标星 1.5w+,从此我只用这款全能高速下载工具!

    卸载 x 雷某度!GitHub 标星 1.5w+,从此我只用这款全能高速下载工具!作者|Rocky0429来源|Python空间大家好,我是Rocky0429,一个喜欢在网上收集各种资源的蒟蒻…网上资源眼花缭乱,下载的方式也同样千奇百怪,比如BT下载,磁力链接,网盘资源等等等等,下个资源可真不容易,不一样的方式要用不同的下载软件,因此某比较有名的x雷和某度网盘成了我经常使用的工具。作为一个没有钱的穷鬼,某度网盘几十kb的下载速度让我…

  • keepalived 保证集群的高可用

    keepalived 保证集群的高可用

  • ssm框架过时了吗_ssm和mvc框架

    ssm框架过时了吗_ssm和mvc框架日志如果一个数据库操作,出现了异常,我们需要排错,日志就是最好的助手曾经:sout,debug现在:日志工厂掌握STDOUT_LOGGINGLOG4Jlog4j什么是Log4j?我们可以控制日志信息输送的目的地是控制台我们也可以控制每一条日志的输出格式通过定义每一条日志信息的级别,我们能够更加细致地控制日志的生成过程通过一个配置文件来灵活地进行配置,而不需要修改应用的代码。分页减少数据量selsect * from user limit startIndex,pageS

  • 联想笔记本键盘亮了屏幕不亮怎么办_电脑开机显示器和键盘都不亮

    联想笔记本键盘亮了屏幕不亮怎么办_电脑开机显示器和键盘都不亮联想电脑显示器不亮怎么办联想电脑显示器不亮解决方法一:1、开机后,我们先不管显示器是否能正常的亮或显示,我们先再次按主机上的重启键,然后我们按一下键中的“numlock”键,也就是台式键盘右边的数字开关切换键。2、如数字开关键上面的数字锁定灯可以正常的亮或正常的灭,这时就说明电脑主机一般没啥事儿了,基本上可以确定是由显示器本身的问题了。3、如无法显示正常的灯亮和灯灭的话,那么基本可以说明是电脑机…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号