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

算法之记忆化搜索_艾宾浩斯记忆曲线的算法实现记忆化搜索其实就是暴力搜索的过程中保存一些已经计算过的状态(思想类似于动态规划,保存计算过的状态),在暴力搜索的过程中利用这些计算过的状态从而减少很大程度上的计算,从而达到时间复杂度上的优化。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)


相关推荐

  • ElasticJob分布式调度,分布式多个微服务执行只需要执行一个定时任务,基本概念介绍(一)「建议收藏」

    ElasticJob分布式调度,分布式多个微服务执行只需要执行一个定时任务,基本概念介绍(一)「建议收藏」ElasticJob分布式调度,分布式多个微服务执行只需要执行一个定时任务,基本概念介绍(一)

    2022年10月25日
  • Oracle实用操作(三)oracle 表名长度的限制

    Oracle实用操作(三)oracle 表名长度的限制Oracle实用操作(三)oracle表名长度的限制1、在新建oracle表的时候,经过查找相关资料oracle表名的最大长度是30,我加上了0331正好是30,多加2为就32了,当然报错了。2、同时有网友说看看descuser_tables,看table_name字段的定义也可以发现,这个很有道理,于是我看了一把.这么看来,表空间名最大长度也是30。看来oracle对30,情有独钟嘛。…

  • CTF misc之流量分析题套路总结[通俗易懂]

    CTF misc之流量分析题套路总结[通俗易懂]1.前言昨天去I春秋刷了几题流量分析题,然后总结了一下流量分析题的做题方法。2.刷题2.1可恶的黑客步骤一、HTTP追踪流先了解进行什么操作可以看到是传了webshell然后进行文件操作套路1:一般是传webshell然后菜刀连接,参数进行base64位加密,先解密参数,了解进行了什么操作一步步解密请求参数了解进行什么操作这个是传webshell里

  • java开发工程师简历模板,2022最新「建议收藏」

    模块科技招聘官莅临千锋教育招聘Java开发工程师招聘官谢经理莅临千锋教育成都分校招聘10位Java开发工程师,谢经理在面试前的宣讲会上,为学员详细介绍了模块科技的发展现状和岗位需求,让学员对公司和岗位有了充分的认识。在随后的面试环节,学员们基于对企业的了解和自身职业发展规划,纷纷递交上自己的简历。年薪120W的架构师简历你见过吗?java程序员该如何达到?这可以归因于Java是德国对于软件工程师来说,因为它用于为许多行业构建高可伸缩性的应用程序。大多数企业服务依赖于Java来支持企业日常那年薪1

  • Redis的数据过期清除策略 与 内存淘汰策略

    Redis的数据过期清除策略 与 内存淘汰策略

  • 合成控制法原理

    合成控制法原理合成控制法反事实思维是**鲁宾反事实分析框架(Rubin’scounterfactualframework)**下进行思考,本质思想是为处理组(treatedgroup)找到一个合适的控制组(controlgroup)。合成控制法的思想是对于处理组,选择与处理组具有相似特征且未受到政策干预的控制组。通过对若干个控制区进行线性组合,构造一个近似处理组的合成控制区域(syntheticcontrolregion).对于未受政策影响的潜在控制组(donorpool),通过权重向量给控制组内每

发表回复

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

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