算法之记忆化搜索_艾宾浩斯记忆曲线的算法实现

算法之记忆化搜索_艾宾浩斯记忆曲线的算法实现记忆化搜索其实就是暴力搜索的过程中保存一些已经计算过的状态(思想类似于动态规划,保存计算过的状态),在暴力搜索的过程中利用这些计算过的状态从而减少很大程度上的计算,从而达到时间复杂度上的优化。1【问题描述】 小明想知道,满足以下条件的正整数序列的数量: 1.第一项为n; 2.第二项不超过n; 3.从第三项开始,每一项小于前两项的差的绝对值。 请计算,对于给定的n,有多少种满足条件的序列。【输入格式】 输入一行包含一个整数n。【输出格式】 输出一个整数,表示答案。答案可能很大

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

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

1.记忆化搜索定义

  • 其实就是暴力搜索的过程中保存一些已经计算过的状态(思想类似于动态规划,保存计算过的状态),在暴力搜索的过程中利用这些计算过的状态从而减少很大程度上的计算,从而达到时间复杂度上的优化。

2.经典题目

2.1 经典题目1

【问题描述】自定义函数w(a,b,c)。
如果 a ≤ 0 或b ≤ 0 或 c ≤ 0, 则返回结果: 1;
如果 a > 20 或 b > 20 或 c > 20, 则返回结果: w(20, 20, 20);
如果 a < b 且 b < c, 则返回结果: w(a, b, c-1) + w(a, b-1, c-1) – w(a, b-1, c)
否则返回结果: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) – w(a-1, b-1, c-1)
【输入格式】 输入三个值a,b,c
【输出格式】对应的函数的返回结果
【输入样例1】2 2 2
【输出样例1】4
【输入样例2】10 4 6
【输出样例2】523

  • 思路:拿到这个题,首先可以想到的就是递归的方法,看上去用递归可以轻而易举的解决,但是递归的开销是不一般的大,并且有大量的重复计算,因此,我们可以采用记忆化搜索的方法记录下前面计算过的数据,以便下次调用。
  • 参考代码:
#include<bits/stdc++.h>
using namespace std;
const int N=25;
int dp[N][N][N];
int dfs(int a,int b,int c){ 
   
	if(a<=0||b<=0||c<=0) return 1;
	if(a>20||b>20||b>20) return dfs(20,20,20);
	//避免重复计算
	if(dp[a][b][c]) return dp[a][b][c];
	if(a<b&&b<c){ 
   
		dp[a][b][c]=dfs(a,b,c-1)+dfs(a,b-1,c-1)-dfs(a,b-1,c);
	}else{ 
   
		dp[a][b][c]=dfs(a-1,b,c)+dfs(a-1,b-1,c)
		+dfs(a-1,b,c-1)-dfs(a-1,b-1,c-1);
	}
	return dp[a][b][c];
}
int main()
{ 
   
	int a,b,c;
	cin>>a>>b>>c;
	cout<<dfs(a,b,c);
	return 0;
} 

3.相关应用

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

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

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

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

(0)


相关推荐

  • 台式硬盘接口详解_台式机主板硬盘接口

    台式硬盘接口详解_台式机主板硬盘接口2016-12-1612:16:44扩展分区类似于一个完整的硬盘,必须进一步分区才能使用。但每个扩展分区中只能存在一个其他分区。此分区在DOS/Windows环境中即为逻辑盘。因此每一个扩展分区的分区表(同样存储在扩…2016-12-2413:34:30你好这个简单方法如下:1、把SATA数据线的一头,插在主板的SATA接口上。如果有多块硬盘,要把启动盘接在第一个口上。如果硬盘是sat…

    2022年10月31日
  • 越权访问漏洞总结

    越权访问漏洞总结一、平行越权攻击者请求操作(增删改查)某条数据时,web应用程序没有判断该条数据的所属人,或者在判断数据所属人时直接从用户提交的表单参数中获取,例如用户id等,导致攻击者可以自行修改参数,操作获取不属于自己的数据。测试方法:在发送请求时观察请求参数,尝试修改用户id或者其他参数验证是否能查看不属于自己的数据,进行增删改查,若成功则存在平行越权的漏洞。 二、纵向越权和平行越权相似…

  • 开源!!!100 多个常用 API 数据接口免费分享!建议收藏![通俗易懂]

    开源!!!100 多个常用 API 数据接口免费分享!建议收藏![通俗易懂]点击上方“Java精选”,选择“设为星标”别问别人为什么,多问自己凭什么!下方有惊喜留言必回,有问必答!每天08:15更新文章,每天进步一点点…我们在开发的过程中,常常调用API接口,往往事半功倍。今天给大家整理了优秀的API接口!各类无次数限制的免费API接口整理,主要是聚合数据上和APIStore上的一些,还有一些其他的。聚合数据提供30大类,160种以上基…

  • 怎样从数组中删除给定元素_java数组包含某个元素

    怎样从数组中删除给定元素_java数组包含某个元素packageday21;importjava.util.Scanner;//调用Scanner一个简单的文本扫描器importstaticnet.mindview.util.Print.*;importjava.util.Random;publicclassShow{publicstaticvoidmain(String[]args){int[]a={0,1,2,3};for(inti:a).

  • LSTM 时间序列预测 matlab

    由于参加了一个小的课题,是关于时间序列预测的。平时习惯用matlab,网上这种资源就比较少。借鉴了 http://blog.csdn.net/u010540396/article/details/52797489 的内容,稍微修改了一下程序。程序说明:DATA.mat是一行时序值,numdely是用前numdely个点预测当前点,cell_num是隐含层的数目,cos

  • stringutil.isnotempty_中低腰和低腰的区别

    stringutil.isnotempty_中低腰和低腰的区别
    转自:http://www.zhenhua.org/article.asp?id=625
     
    isNotEmpty将空格也作为参数,isNotBlank则排除空格参数

    参考QuoteStringUtils方法的操作对象是java.lang.String类型的对象,是JDK提供的String类型操作方法的补充,并且是null安全的(即如果输入参数String为null则不会抛出NullPointerException,而是做了相应处理,例如,如果输入为

发表回复

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

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