[已解决]Python：每日一题 349

zltzlt

今天的题目：

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。

可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格，直到到达棋盘的右下角。

给定一个棋盘 grid 包含每个礼物的价值，计算最多能拿到多少价值的礼物。

示例 1:

输入：
[
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]
输出：12
解释：路径 1→3→5→2→1 可以拿到最多价值的礼物

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

tzczjh

2020-3-12 07:36:05

1. def solve(chessboard):
   
2.     # 简单dp
   
3.     # dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + chessboard[i][j]
   
4.     # 每个chessboard[i][j]只被访问一次 所以可以用chessboard[i][j]存储dp[i][j]的值
   
5. 
   
6.     m = len(chessboard)
   
7.     if not m:
   
8.         return None
   
9.     n = len(chessboard[0])
   
10. 
    
11.     for i in range(m):
    
12.         for j in range(n):
    
13.             if not (i + j):
    
14.                 continue
    
15.             if not i:
    
16.                 chessboard[i][j] += chessboard[i][j - 1]
    
17.             elif not j:
    
18.                 chessboard[i][j] += chessboard[i - 1][j]
    
19.             else:
    
20.                 chessboard[i][j] += max(chessboard[i][j - 1], chessboard[i - 1][j])
    
21.     return chessboard[m - 1][n - 1]

复制代码

跳转到最佳答案楼层

zltzlt

TJBEST 发表于 2020-3-11 13:31
高亮而且有奇怪的字符

这么快？乱码已调整

zltzlt

TJBEST 发表于 2020-3-11 14:29
此法比较费空间，但是时间上还是不慢的。

96 ms

zltzlt

Geoffreylee 发表于 2020-3-11 15:24

56 ms

zltzlt

风魔孤行者 发表于 2020-3-11 15:34
自己都有点看不下去

输入以下数据超时：

1. [[7, 0, 8, 8, 0, 3, 5, 8, 5, 4], [4, 1, 2, 9, 9, 6, 0, 8, 6, 9], [9, 7, 1, 1, 0, 1, 2, 4, 1, 7]]

复制代码

zltzlt

mdphd 发表于 2020-3-11 15:35
这个算法在m，n很大时应该会很快

60 ms

zltzlt

kinkon 发表于 2020-3-11 15:57
不好意思上传...

70 ms

zltzlt

风魔孤行者 发表于 2020-3-11 16:23
大佬，看了你的代码之后写的

输入以下数据超时：

1. [[7, 1, 3, 5, 8, 9, 9, 2, 1, 9, 0, 8, 3, 1, 6, 6, 9, 5], [9, 5, 9, 4, 0, 4, 8, 8, 9, 5, 7, 3, 6, 6, 6, 9, 1, 6], [8, 2, 9, 1, 3, 1, 9, 7, 2, 5, 3, 1, 2, 4, 8, 2, 8, 8], [6, 7, 9, 8, 4, 8, 3, 0, 4, 0, 9, 6, 6, 0, 0, 5, 1, 4], [7, 1, 3, 1, 8, 8, 3, 1, 2, 1, 5, 0, 2, 1, 9, 1, 1, 4], [9, 5, 4, 3, 5, 6, 1, 3, 6, 4, 9, 7, 0, 8, 0, 3, 9, 9], [1, 4, 2, 5, 8, 7, 7, 0, 0, 7, 1, 2, 1, 2, 7, 7, 7, 4], [3, 9, 7, 9, 5, 8, 9, 5, 6, 9, 8, 8, 0, 1, 4, 2, 8, 2], [1, 5, 2, 2, 2, 5, 6, 3, 9, 3, 1, 7, 9, 6, 8, 6, 8, 3], [5, 7, 8, 3, 8, 8, 3, 9, 9, 8, 1, 9, 2, 5, 4, 7, 7, 7], [2, 3, 2, 4, 8, 5, 1, 7, 2, 9, 5, 2, 4, 2, 9, 2, 8, 7], [0, 1, 6, 1, 1, 0, 0, 6, 5, 4, 3, 4, 3, 7, 9, 6, 1, 9]]

复制代码

zltzlt

flamezyy 发表于 2020-3-11 16:33
估计超时了

嗯，输入以下数据超时：

1. [[7, 1, 3, 5, 8, 9, 9, 2, 1, 9, 0, 8, 3, 1, 6, 6, 9, 5], [9, 5, 9, 4, 0, 4, 8, 8, 9, 5, 7, 3, 6, 6, 6, 9, 1, 6], [8, 2, 9, 1, 3, 1, 9, 7, 2, 5, 3, 1, 2, 4, 8, 2, 8, 8], [6, 7, 9, 8, 4, 8, 3, 0, 4, 0, 9, 6, 6, 0, 0, 5, 1, 4], [7, 1, 3, 1, 8, 8, 3, 1, 2, 1, 5, 0, 2, 1, 9, 1, 1, 4], [9, 5, 4, 3, 5, 6, 1, 3, 6, 4, 9, 7, 0, 8, 0, 3, 9, 9], [1, 4, 2, 5, 8, 7, 7, 0, 0, 7, 1, 2, 1, 2, 7, 7, 7, 4], [3, 9, 7, 9, 5, 8, 9, 5, 6, 9, 8, 8, 0, 1, 4, 2, 8, 2], [1, 5, 2, 2, 2, 5, 6, 3, 9, 3, 1, 7, 9, 6, 8, 6, 8, 3], [5, 7, 8, 3, 8, 8, 3, 9, 9, 8, 1, 9, 2, 5, 4, 7, 7, 7], [2, 3, 2, 4, 8, 5, 1, 7, 2, 9, 5, 2, 4, 2, 9, 2, 8, 7], [0, 1, 6, 1, 1, 0, 0, 6, 5, 4, 3, 4, 3, 7, 9, 6, 1, 9]]

复制代码

zltzlt

塔利班 发表于 2020-3-11 16:47

92 ms

zltzlt

ouyunfu 发表于 2020-3-11 19:18

输入以下数据超时：

1. [[7, 1, 3, 5, 8, 9, 9, 2, 1, 9, 0, 8, 3, 1, 6, 6, 9, 5], [9, 5, 9, 4, 0, 4, 8, 8, 9, 5, 7, 3, 6, 6, 6, 9, 1, 6], [8, 2, 9, 1, 3, 1, 9, 7, 2, 5, 3, 1, 2, 4, 8, 2, 8, 8], [6, 7, 9, 8, 4, 8, 3, 0, 4, 0, 9, 6, 6, 0, 0, 5, 1, 4], [7, 1, 3, 1, 8, 8, 3, 1, 2, 1, 5, 0, 2, 1, 9, 1, 1, 4], [9, 5, 4, 3, 5, 6, 1, 3, 6, 4, 9, 7, 0, 8, 0, 3, 9, 9], [1, 4, 2, 5, 8, 7, 7, 0, 0, 7, 1, 2, 1, 2, 7, 7, 7, 4], [3, 9, 7, 9, 5, 8, 9, 5, 6, 9, 8, 8, 0, 1, 4, 2, 8, 2], [1, 5, 2, 2, 2, 5, 6, 3, 9, 3, 1, 7, 9, 6, 8, 6, 8, 3], [5, 7, 8, 3, 8, 8, 3, 9, 9, 8, 1, 9, 2, 5, 4, 7, 7, 7], [2, 3, 2, 4, 8, 5, 1, 7, 2, 9, 5, 2, 4, 2, 9, 2, 8, 7], [0, 1, 6, 1, 1, 0, 0, 6, 5, 4, 3, 4, 3, 7, 9, 6, 1, 9]]

复制代码

zltzlt

Unicorn# 发表于 2020-3-11 19:50

解答错误

输入：

1. [[1, 2, 3], [4, 5, 6]]

复制代码

输出：11
预期结果：16

zltzlt

archlzy 发表于 2020-3-11 20:26

88 ms

zltzlt

l0stparadise 发表于 2020-3-12 00:44
现学了itertools。。。。

输入以下数据超时：

1. [[1, 4, 8, 6, 2, 2, 1, 7], [4, 7, 3, 1, 4, 5, 5, 1], [8, 8, 2, 1, 1, 8, 0, 1], [8, 9, 2, 9, 8, 0, 8, 9], [5, 7, 5, 7, 1, 8, 5, 5], [7, 0, 9, 4, 5, 6, 5, 6], [4, 9, 9, 7, 9, 1, 9, 0]]

复制代码

zltzlt

派生小生 发表于 2020-3-12 01:24

60 ms

zltzlt

tzczjh 发表于 2020-3-12 07:36

56 ms

zltzlt

776667 发表于 2020-3-12 10:52

输入以下数据出错：

1. [[1, 2, 5], [3, 2, 1]]

复制代码

zltzlt

fan1993423 发表于 2020-4-17 02:06

要返回一个整数

zltzlt

fan1993423 发表于 2020-4-18 14:59
本来都写好lst[-1][-1]，最后调试的时候不知道怎么回事，删了，已改

58 ms