[蓝桥杯python] 拿金币:有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到

本文主要是介绍[蓝桥杯python] 拿金币:有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 [蓝桥杯python] 拿金币

问题描述

1、资源限制

2、输入格式

3、输出格式

4、样式输入及输出

5、代码及解析

大功告成!编写不易,大家成功后点个关注or赞谢谢~~


问题描述

  有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。


1、资源限制

资源限制

时间限制:1.0s   内存限制:256.0MB

*此处要特别注意,因为平时的题都是512MB,这次只有256MB所以要考虑时间复杂度*

2、输入格式

第一行输入一个正整数n。
以下n行描述该方格。金币数保证是不超过1000的正整数。

3、输出格式

最多能拿金币数量。

4、样式输入及输出

样例输入

3
1 3 3
2 2 2
3 1 2

样例输出

11

5、代码及解析

具体解析请大家自己看一下代码中的备注,在此不多做解释。

结果:

n = int(input())
rect = []
#将所有的输入组成数组
for i in range(0, n):rect.append(input().split())
#此处将(1,1)的数单独转化为整型,后面的话就可以从(2,2开始计算)
rect[0][0] = int(rect[0][0])
#由于考虑到时间复杂度,此处的话将边界的数单独算出来,不然后面时间复杂度过高。
for i in range(1,n):rect[0][i] = int(rect[0][i]) + int(rect[0][i-1])
for i in range(1, n):rect[i][0] = int(rect[i][0]) + int(rect[i-1][0])
#接下来就开始计算从(2,2)的金币累加
for i in range(1, n):for j in range(1, n):rect[i][j] = int(rect[i][j]) + max(int(rect[i-1][j]),int(rect[i][j-1]))
#最后输出数组最后一个数就是最大的利益
print(rect[-1][-1])

 

但是可以看出,时间复杂度还是有点高,但是可以解决问题

希望有大神可以在评论区提提优化意见,大家一起努力 !!!


自己写的所以有点复杂,但是至少能完成嘿嘿。如果各位有优化欢迎评论区讨论!!

大功告成!编写不易,大家成功后点个关注or赞谢谢~~


这篇关于[蓝桥杯python] 拿金币:有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/592405

相关文章

python panda库从基础到高级操作分析

《pythonpanda库从基础到高级操作分析》本文介绍了Pandas库的核心功能,包括处理结构化数据的Series和DataFrame数据结构,数据读取、清洗、分组聚合、合并、时间序列分析及大数据... 目录1. Pandas 概述2. 基本操作:数据读取与查看3. 索引操作:精准定位数据4. Group

Python pandas库自学超详细教程

《Pythonpandas库自学超详细教程》文章介绍了Pandas库的基本功能、安装方法及核心操作,涵盖数据导入(CSV/Excel等)、数据结构(Series、DataFrame)、数据清洗、转换... 目录一、什么是Pandas库(1)、Pandas 应用(2)、Pandas 功能(3)、数据结构二、安

Python使用Tenacity一行代码实现自动重试详解

《Python使用Tenacity一行代码实现自动重试详解》tenacity是一个专为Python设计的通用重试库,它的核心理念就是用简单、清晰的方式,为任何可能失败的操作添加重试能力,下面我们就来看... 目录一切始于一个简单的 API 调用Tenacity 入门:一行代码实现优雅重试精细控制:让重试按我

Python安装Pandas库的两种方法

《Python安装Pandas库的两种方法》本文介绍了三种安装PythonPandas库的方法,通过cmd命令行安装并解决版本冲突,手动下载whl文件安装,更换国内镜像源加速下载,最后建议用pipli... 目录方法一:cmd命令行执行pip install pandas方法二:找到pandas下载库,然后

Python实现网格交易策略的过程

《Python实现网格交易策略的过程》本文讲解Python网格交易策略,利用ccxt获取加密货币数据及backtrader回测,通过设定网格节点,低买高卖获利,适合震荡行情,下面跟我一起看看我们的第一... 网格交易是一种经典的量化交易策略,其核心思想是在价格上下预设多个“网格”,当价格触发特定网格时执行买

Python标准库之数据压缩和存档的应用详解

《Python标准库之数据压缩和存档的应用详解》在数据处理与存储领域,压缩和存档是提升效率的关键技术,Python标准库提供了一套完整的工具链,下面小编就来和大家简单介绍一下吧... 目录一、核心模块架构与设计哲学二、关键模块深度解析1.tarfile:专业级归档工具2.zipfile:跨平台归档首选3.

使用Python构建智能BAT文件生成器的完美解决方案

《使用Python构建智能BAT文件生成器的完美解决方案》这篇文章主要为大家详细介绍了如何使用wxPython构建一个智能的BAT文件生成器,它不仅能够为Python脚本生成启动脚本,还提供了完整的文... 目录引言运行效果图项目背景与需求分析核心需求技术选型核心功能实现1. 数据库设计2. 界面布局设计3

Python进行JSON和Excel文件转换处理指南

《Python进行JSON和Excel文件转换处理指南》在数据交换与系统集成中,JSON与Excel是两种极为常见的数据格式,本文将介绍如何使用Python实现将JSON转换为格式化的Excel文件,... 目录将 jsON 导入为格式化 Excel将 Excel 导出为结构化 JSON处理嵌套 JSON:

Python操作PDF文档的主流库使用指南

《Python操作PDF文档的主流库使用指南》PDF因其跨平台、格式固定的特性成为文档交换的标准,然而,由于其复杂的内部结构,程序化操作PDF一直是个挑战,本文主要为大家整理了Python操作PD... 目录一、 基础操作1.PyPDF2 (及其继任者 pypdf)2.PyMuPDF / fitz3.Fre

python设置环境变量路径实现过程

《python设置环境变量路径实现过程》本文介绍设置Python路径的多种方法:临时设置(Windows用`set`,Linux/macOS用`export`)、永久设置(系统属性或shell配置文件... 目录设置python路径的方法临时设置环境变量(适用于当前会话)永久设置环境变量(Windows系统