洛谷_P1464 Function_python写法

目录

1.错误解法

2.学习记忆化搜索算法

2.1简介

2.2案例学习

3.解法

4.总结


1.错误解法

a = 0
b = 0
c = 0
def w(a,b,c):if a<=0 or b<=0 or c<=0:return 1elif a>20 or b>20 or c>20:return w(20,20,20)elif a<b and b<c:return w(a-1,b,c) + w(a-1,b,c) + w(a-1,b,c-1) -w(a-1,b-1,c-1)else:return w(a-1,b,c) + w(a-1,b-1,c) + w(a-1,b,c-1) - w(a-1,b-1,c-1)
while 1:a, b, c = map(int, input().split(' '))if a==-1 and b==-1 and c==-1:breakelse:print(f'w({a}, {b}, {c}) = {w(a,b,c)}')

 

直接按照题目地意思来做地话,就会超时。

怎么优化,我也不会,那就先去学习吧。再见

看到网上的C++解法说用的是记忆化搜索算法,那就先学习一下看看记忆化算法是个什么事儿。

2.学习记忆化搜索算法

2.1简介

        看完网上有挂记忆化算法的介绍之后,我的胡说八道是,记忆化算法是一种动态规划算法,它能够存储已经计算过的状态信息,避免造成重复计算,从而能够提高算法的效率。 

        看到网上有一个更加生动的解释,所谓的记忆化搜索可以理解为是拥有一个备忘录的递归,而记忆化的实现就是通过这个备忘录,在每次进入递归的时候都会先看看备忘录中是否已经计算了,如果没有就计算,有的话就可以直接使用。

2.2案例学习

思路:

1.定义一个备忘录;

2.每次进入递归,看看备忘录是否有;

3.如果没有,每次返回的时候,将计算的值加入备忘录中。

定义备忘录在python中我们可以利用列表来实现。

在定义列表的时候代码中用到了列表推导式,列表推导式

Python进阶:列表推导式(List Comprehension) - 知乎 (zhihu.com)

n = int(input())def fib(n):l = [0 for i in range(n+1)]return fib_helper(l,n)def fib_helper(l,n):if n == 0 or n == 1:return nif l[n] == 0:l[n] = fib_helper(l,n-1) + fib_helper(l,n-2)return l[n]else:return l[n]print(fib(n))

3.解法

         终于给写出来了,大家一定要认真看题目,计算错了让我找错误找了好久好久呜呜呜呜呜....

        我这里定义的备忘录就是一个三维的列表,关于三维列表的访问大家可以自己尝试写一个简单的三维列表,然后看看他是怎么访问的。

        关于内部的判断,如果按照以前的进行嵌套判断的话,还是会超时,所以就增加了一个并列条件:

elif l[a][b][c]:
        return l[a][b][c]

data = []
l = [[[0 for _ in range(21)] for _ in range(21)] for _ in range(21)]
def w_helper(a,b,c):if a <= 0 or b <= 0 or c <= 0:return 1elif a > 20 or b > 20 or c > 20:return w_helper(20,20,20)elif l[a][b][c]:return l[a][b][c]elif a<b and b<c:l[a][b][c] = w_helper(a,b,c-1) + w_helper(a,b-1,c-1) - w_helper(a,b-1,c)else:l[a][b][c] = w_helper(a-1,b,c) + w_helper(a-1,b-1,c) + w_helper(a-1,b,c-1) - w_helper(a-1,b-1,c-1)return l[a][b][c]while True:a, b, c = map(int, input().split(' '))data.append([a,b,c])if a == -1 and b == -1 and c == -1:data.pop()break
for i in data:print(f'w({i[0]}, {i[1]}, {i[2]}) = {w_helper(i[0], i[1], i[2])}')

4.总结

        理解这个算法并不难,就是要认真看题目,题目看错了一直以为是自己写的算法写错了,好在最后终于写出来了。

        以前学C++的时候其实就是没有耐心去学习,导致我一直都觉得很难,其实我对记忆化搜索算法的理解大概就是存储到列表(其他)遍历的算法。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/252841.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

1、将 ChatGPT 集成到数据科学工作流程中:提示和最佳实践

将 ChatGPT 集成到数据科学工作流程中:提示和最佳实践 希望将 ChatGPT 集成到您的数据科学工作流程中吗?这是一个利用 ChatGPT 进行数据科学的提示的实践。 ChatGPT、其继任者 GPT-4 及其开源替代品非常成功。开发人员和数据科学家都希望提高工作效率,并使用 ChatGPT 来简…

LRU缓存

有人从网络读数据&#xff0c;有人从磁盘读数据&#xff0c;机智的人懂得合理利用缓存加速数据的读取效率&#xff0c;提升程序的性能&#xff0c;搏得上司的赏识&#xff0c;赢得白富美的青睐&#xff0c;进一步走向人生巅峰~ LRU假说 LRU缓存&#xff08;Least Recently Used…

2023 巅峰之作 | AIGC、AGI、GhatGPT、人工智能大语言模型的崛起与挑战

文章目录 01 《ChatGPT 驱动软件开发》内容简介 02 《ChatGPT原理与实战》内容简介 03 《神经网络与深度学习》04 《AIGC重塑教育》内容简介 05 《通用人工智能》目  录 2023年是人工智能大语言模型大爆发的一年&#xff0c;一些概念和英文缩写也在这一年里集中出现&#xff…

12.0 Zookeeper 数据同步流程

在 Zookeeper 中&#xff0c;主要依赖 ZAB 协议来实现分布式数据一致性。 ZAB 协议分为两部分&#xff1a; 消息广播崩溃恢复 消息广播 Zookeeper 使用单一的主进程 Leader 来接收和处理客户端所有事务请求&#xff0c;并采用 ZAB 协议的原子广播协议&#xff0c;将事务请求…

10英寸安卓车载平板电脑丨ONERugged车载工业平板:解决农业工作效率

农业是人类社会的基石之一&#xff0c;而农业工作效率的提升一直是农民和农业专业人士关注的重要议题。随着技术的不断进步&#xff0c;车载工业平板成为了解决农业工作效率的创新解决方案。本文将探讨车载工业平板如何为农业带来巨大的改变&#xff0c;提高农民的工作效率和农…

JavaEE企业级应用软件开发—Spring框架入门学习笔记(一)

一、认识框架 实际开发中&#xff0c;随着业务的发展&#xff0c;软件系统变得越来越复杂&#xff0c;如果所有的软件都从底层功能开始开发&#xff0c;那将是一个漫长而繁琐的过程。此外&#xff0c;团队协作开发时&#xff0c;由于没有统一的调用规范&#xff0c;系统会出现大…

幻兽帕鲁怎么样?好玩? Mac版的玩《幻兽帕鲁》也很简单,只需三个步骤

幻兽帕鲁怎么样 幻兽帕鲁是一款集合了多种游戏元素的游戏&#xff0c;它巧妙地融合了《方舟:生存进化》的野外生存挑战、《荒野之息》的开放世界探索、《魔兽世界》的多元角色互动以及宝可梦的精灵捕捉与培养等经典游戏元素。游戏的核心系统是「帕鲁」捕获&#xff0c;你可以让…

MySQL-存储引擎

文章目录 1. MySQL的体系结构2. 存储引擎2.1 存储引擎概述2.2 存储引擎的类型及选择方案2.3 操作存储引擎2.4 InnoDB存储引擎2.4.1 逻辑存储结构2.4.2 架构2.4.2.1 内存结构2.4.2.2 磁盘结构2.4.2.3 后台线程 2.4.3 事务2.4.3.1 Undo Log&#xff08;原子性&#xff09;2.4.3.2…

C语言其他类型的数组

1.字符数组 概念&#xff1a;专门存放字符的数组&#xff0c;称为字符数组初始化与元素引用&#xff1a; char s1[5] {a, b, c, d, e}; // s1存放的是字符序列&#xff0c;非字符串 char s2[6] {a, b, c, d, e, \0}; // s2存放了一个字符串char s[6] {"abcde&q…

【证书管理】实验报告

证书管理实验 【实验环境】 ISES客户端 【实验步骤】 查看证书 查看证书详细信息 选择任意证书状态&#xff0c;在下方“证书列表”中出现符合要求的所有证书。在“证书列表”中点击要查看证书&#xff0c;在右侧“证书详细信息”栏出现被选证书信息。 上述操作如图1.2.…

Maven详细配置整理

Maven的作用 在Javaweb开发中&#xff0c;需要使用大量的jar包&#xff0c;需要手动去导入&#xff0c;Maven能够自动帮我们导入和配置这个jar包。 对于新手Maven就是用来方便导入jar包的&#xff01; Maven的核心思想&#xff1a;约定大于配置 有约束&#xff0c;不要去违…

Jmeter 01 -概述线程组

1、Jmeter:概述 1.1 是什么&#xff1f; Jmeter是Apache公司使用Java 开发的一款测试工具 1.2 为什么&#xff1f; 高效、功能强大 模拟一些高并发或多次循环等特殊场景 1.3 怎么用&#xff1f; 下载安装 1、下载jmeter&#xff0c;解压缩2、安装Java环境&#xff08;jmet…

力扣53. 最大子数组和(滑动窗口,动态规划)

Problem: 53. 最大子数组和 文章目录 题目描述思路及解法复杂度Code 题目描述 思路及解法 思路1:滑动窗口 1.为求出最大连续的子数组和,我们逻辑上假设有一个窗口在原数组上滑动, 欲求出最大连续,则需要保证窗口中的所有元素和最起码大于0; 2.即当当前窗口中的元素值的和小于0…

从零开始手写mmo游戏从框架到爆炸(六)— 消息处理工厂

就好像门牌号一样&#xff0c;我们需要把消息路由到对应的楼栋和楼层&#xff0c;总不能像菜鸟一样让大家都来自己找数据吧。 首先这里我们参考了rabbitmq中的topic与tag模型&#xff0c;topic对应类&#xff0c;tag对应方法。 新增一个模块&#xff0c;专门记录路由eternity-…

深入探索 Stable Diffusion:AI图像创新的新纪元

深入探索 Stable Diffusion&#xff1a;AI图像创新的新纪元 介绍 Stable Diffusion 的核心功能和应用场景Stable Diffusion 架构解析深入 Stable Diffusion 的关键组件变分自编码器&#xff08;VAE&#xff09;生成对抗网络&#xff08;GAN&#xff09;注意力机制优化算法数据集…

泛型、Trait 和生命周期(上)

目录 1、提取函数来减少重复 2、在函数定义中使用泛型 3、结构体定义中的泛型 4、枚举定义中的泛型 5、方法定义中的泛型 6、泛型代码的性能 每一门编程语言都有高效处理重复概念的工具。在 Rust 中其工具之一就是 泛型&#xff08;generics&#xff09;。泛型是具体类型…

GEE Colab——如何利用Matplotlib在colab中进行图形制作

在colab中绘制图表 笔记本的一个常见用途是使用图表进行数据可视化。Colaboratory 提供多种图表工具作为 Python 导入,让这一工作变得简单。 Matplotlib Matplotlib 是最常用的图表工具包,详情请查看其文档,并通过示例获得灵感。 线性图 线性图是一种常见的图表类型,用…

C++迷宫游戏详解

个人主页&#xff1a;[PingdiGuo_guo] 收录专栏&#xff1a;[C干货专栏] 大家好呀&#xff0c;我是PingdiGuo_guo&#xff0c;今天我们来学习用C实现一个迷宫游戏。 目录 1.迷宫的具体步骤 1.1.迷宫的初始化 1.2.寻路算法 1.DFS算法 2.BFS算法 1.3.移动 2.总结 C迷宫游…

[晓理紫]每日论文分享(有中文摘要,源码或项目地址)--强化学习、模仿学习、机器人

专属领域论文订阅 关注{晓理紫|小李子}&#xff0c;每日更新论文&#xff0c;如感兴趣&#xff0c;请转发给有需要的同学&#xff0c;谢谢支持 如果你感觉对你有所帮助&#xff0c;请关注我&#xff0c;每日准时为你推送最新论文。 为了答谢各位网友的支持&#xff0c;从今日起…

SpringCloud-创建多模块项目

在微服务架构中&#xff0c;项目的组织结构对于代码的维护和团队的协作至关重要。Spring Cloud作为一个强大的微服务框架&#xff0c;提供了丰富的功能和组件&#xff0c;同时也支持多模块项目的创建&#xff0c;使得代码结构更加清晰、易于管理。本文将介绍如何使用 Spring Cl…