记忆化搜索简介「建议收藏」

记忆化搜索简介「建议收藏」记忆化搜索:算法上依然是搜索的流程,但是搜索到的一些解用动态规划的那种思想和模式作一些保存。一般说来,动态规划总要遍历所有的状态,而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝,可能剪去大量不必要的状态,因此在空间开销上往往比动态规划要低很多。记忆化算法在求解的时候还是按着自顶向下的顺序,但是每求解一个状态,就将它的解保存下来,以后再次遇到这个状态的时候,就不必重新求解了。

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

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

记忆化搜索:算法上依然是搜索的流程,但是搜索到的一些解用动态规划的那种思想和模式作一些保存。
一般说来,动态规划总要遍历所有的状态,而搜索可以排除一些无效状态。
更重要的是搜索还可以剪枝,可能剪去大量不必要的状态,因此在空间开销上往往比动态规划要低很多。
记忆化算法在求解的时候还是按着自顶向下的顺序,但是每求解一个状态,就将它的解保存下来,
以后再次遇到这个状态的时候,就不必重新求解了。
这种方法综合了搜索和动态规划两方面的优点,因而还是很有实用价值的。

这种方法做题有时比动态规划还简便。

下面是一个记忆化搜索的例题:


爬楼梯

有一个n阶的楼梯,每一次可以上1阶或2阶,有多少种方法?

#include<stdio.h>

long long x[10010],y[10010];
long long Mesch(int i) //Mesch 为 Memory search 记忆化搜索 
{
	int j;
	if(i==1) return 1;
	if(i==2) return 2;
	if(y[i]>0) return y[i]; //记忆化搜索 
	y[i]=Mesch(i-1)+Mesch(i-2);
	return y[i]; 
}
int main()
{
	int n;
	scanf("%d",&n);
	printf("%I64d",Mesch(n));
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/164451.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • nginx与uWSGI[通俗易懂]

    nginx与uWSGI[通俗易懂]今天同事问了我一个问题,nginx和uWSGI的区别是啥?我当时答出了反向代理和静态文件,后来聊到了负载均衡,所以好好查了下两者的区别。首先来了解几个概念:WSGIWSGI的全称是WebServerGatewayInterface(Web服务器网关接口),它不是服务器、python模块、框架、API或者任何软件,只是一种描述web服务器(如nginx,uWSGI等服务器)如何与…

    2022年9月11日
    4
  • vr的开发流程_vr虚拟现实 需要设备

    vr的开发流程_vr虚拟现实 需要设备http://www.unitymanual.com/forum.php?mod=viewthread&tid=31034 原文出自游戏蛮牛本文介绍虚拟现实项目开发流程,共大家参考与学习,也希望各位提出意见…通过将现实中真实存在的构建在虚拟平台上,使得用户可以不在受时间、地点、位置和区域的限制来完成一些操作。=================================开发流程=

    2022年9月13日
    1
  • jmeter基础教程_生活质量和生活品质有什么区别

    jmeter基础教程_生活质量和生活品质有什么区别前言:JMeter一个非常强大的测试工具,给大家简单的介绍一下基本使用方法入门篇,如若不懂,请重新学习小学语文,再来阅读,谢谢!!!1、第一步就安装JMeter,使用JMeter的前提是先把jdk等配置完成,才可以打开JMeter,不然会出现点开没反应的情况我这里展示的是一个改成中文的JMeter,英语好的小伙伴也可以不用改哈默认中文:在jmeter/bin/jmeter.properties在#language=en写入language=zh_CN默认查看结果处理展示编码为u.

    2025年8月24日
    3
  • 一些常用的find命令

    一些常用的find命令

    2021年5月2日
    155
  • 构建vscode的vue组件代码补全插件以及上传

    构建vscode的vue组件代码补全插件以及上传

    2022年4月2日
    335
  • 很好的理解遗传算法的样例

    很好的理解遗传算法的样例

    2021年12月10日
    37

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

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