[蓝桥杯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赞谢谢~~

---