[已解决]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]

复制代码

跳转到最佳答案楼层

TJBEST

高亮而且有奇怪的字符

zltzlt

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

这么快？乱码已调整

mdphd

感觉除了遍历没什么特别高效的算法

mdphd

找到一个好算法！

vidyhe

可是没有说每个单元格是多少价格呢

TJBEST

此法比较费空间，但是时间上还是不慢的。

1. def fun349(grid):
   
2.     m = len(grid)
   
3.     n = len(grid[0])
   
4.     fuzhu = []
   
5.     for index in range(0,m):
   
6.         fuzhu.append([0 for i in range(0,n)])
   
7.    
   
8.     minNum = min([m,n])
   
9.     fuzhu[0][0]=grid[0][0]
   
10.     for index in range(1,n):
    
11.         fuzhu[0][index]=fuzhu[0][index-1]+grid[0][index]
    
12.     for index in range(1,m):
    
13.         fuzhu[index][0]=fuzhu[index-1][0]+grid[index][0]
    
14.     for index in range(1,minNum):
    
15.         for inner in range(index,n):
    
16.             fuzhu[index][inner]=max([fuzhu[index][inner-1],fuzhu[index-1][inner]])+grid[index][inner]
    
17.         for inner in range(index+1,m):
    
18.             fuzhu[inner][index]=max([fuzhu[inner][index-1],fuzhu[inner-1][index]])+grid[inner][index]
    
19.     return fuzhu[m-1][n-1]

复制代码

kinkon

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

人才啊

Geoffreylee

1. def f_349(lst: list) -> int:
   
2.     # 创建与原数组相同大小的0数组，记录到lst[i][j]所得到的最大值
   
3.     max_value_lst = [[0] * len(i) for i in lst]
   
4. 
   
5.     for i in range(len(lst)):
   
6.         for j in range(len(lst[0])):
   
7.             if i == 0 and j == 0:
   
8.                 # 记录初始值
   
9.                 max_value_lst[i][j] = lst[i][j]
   
10.             else:
    
11.                 max_value_lst[i][j] = max(max_value_lst[i-1][j], max_value_lst[i][j-1]) + lst[i][j]
    
12. 
    
13.     return max_value_lst[-1][-1]
    
14. 
    
15. 
    
16. print(f_349([[1, 2, 3], [4, 5, 6], [7, 8, 9]]))

复制代码

风魔孤行者

1. def f(m,n):
   
2.     if m == 0:
   
3.         list1=[]
   
4.         string = 'b'*n
   
5.         list1.append(string)
   
6.         return list1
   
7.     else:      
   
8.         list3 = []
   
9.         for each in f(m-1,n):
   
10.             for number in range(len(each)+1):
    
11.                 list3.append(each[:number]+'a'+each[number:])
    
12.         return list3
    
13. 
    
14. def d(l):
    
15.     list1 = list({}.fromkeys(f((len(l[0])-1),(len(l)-1))).keys())
    
16.     count = []
    
17.     for each in list1:
    
18.         a = 0
    
19.         b = 0
    
20.         n = l[a][b]
    
21.         for value in each:
    
22.             if value == 'a':
    
23.                 b += 1
    
24.                 n += l[a][b]
    
25.             else:
    
26.                 a += 1
    
27.                 n += l[a][b]
    
28.         count.append(n)
    
29.     count.sort()
    
30.     return count.pop()
    
31.         
    
32. print(d([[1,3,1],[1,5,1],[4,2,1]]))         
    
33.    

复制代码

自己都有点看不下去

mdphd

1. a = [
   
2.     [1,3,1],
   
3.     [1,5,1],
   
4.     [4,2,1]
   
5.     ]
   
6. b = [[0]*(max(len(a),len(a[0])))]*(min(len(a),len(a[0])))
   
7. if len(a) <= len(a[0]):
   
8.     b = a
   
9. else:
   
10.     def transformMatrix(m):
    
11.         r = [[] for i in m[0]]
    
12.          
    
13.         for ele in m:
    
14.             for i in range(len(ele)):
    
15.                 r[i].append(ele[i])
    
16.         return r
    
17.     b = transformMatrix(a)
    
18. m, n = len(b), len(b[0])
    
19. c = b[:][:]
    
20. for x in range(1, m):
    
21.     for i in range(1, x):
    
22.         b[i][x-i] = max(b[i - 1][x - i], b[i][x - i - 1]) + c[i][x - i]
    
23.     b[x][0] = b[x - 1][0] +c[x][0]
    
24.     b[0][x] = b[0][x - 1] + c[0][x]
    
25. for x in range(m, n):
    
26.     for i in range(1, m):
    
27.         b[i][x-i] = max(b[i - 1][x - i], b[i][x - i - 1]) + c[i][x - i]
    
28.     b[0][x] = b[0][x - 1] + c[0][x]
    
29. 
    
30. for x in range(n, m + n -1):
    
31.     for i in range(x - n + 1, m):
    
32.         b[i][x-i] = max(b[i - 1][x - i], b[i][x - i -1]) + c[i][x - i]
    
33. print(b[m - 1][n - 1])

复制代码

这个算法在m，n很大时应该会很快

蒋博文

1. def fun349(s):
   
2.     if not s:
   
3.         return 0
   
4.     a = len(s)
   
5.     b = len(s[0])
   
6.     maxs = [0] * b
   
7.     for i in range(0, a):
   
8.         for j in range(0, b):
   
9.             ma = 0
   
10.             mb = 0
    
11.             if i > 0:
    
12.                 mb = maxs[j]
    
13.             if j > 0:
    
14.                 ma = maxs[j - 1]
    
15.                
    
16.             maxs[j] = max(ma, mb) + s[i][j]
    
17.     return maxs[b-1]
    

复制代码

kinkon

不好意思上传...

1. def f349(lst):
   
2.     A, B = len(lst), len(lst[0])
   
3.     t = 1
   
4.     while t < B:
   
5.         lst[0][t] = lst[0][t-1] + lst[0][t]
   
6.         t += 1
   
7.     t = 1
   
8.     while t < A:
   
9.         lst[t][0] = lst[t - 1][0] + lst[t][0]
   
10.         t += 1
    
11.     for i in range(1, A):
    
12.         for j in range(1, B):
    
13.             lst[i][j] = max(lst[i][j] + lst[i][j - 1], lst[i][j] + lst[i - 1][j])
    
14.     return lst[-1][-1]

复制代码

fan1993423

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

思路可以啊， 有什么不好意思上传的

风魔孤行者

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

大佬，看了你的代码之后写的

1. def f(list1,m,n):
   
2.     if m>1 and n>1:
   
3.         return max(f(list1,m-1,n),f(list1,m,n-1))+list1[m-1][n-1]
   
4.     if m==1 and n>1:
   
5.         return f(list1,m,n-1)+list1[m-1][n-1]
   
6.     if m>1 and n==1:
   
7.         return f(list1,m-1,n)+list1[m-1][n-1]
   
8.     if m==1 and n==1:
   
9.         return list1[m-1][n-1]
   
10.    
    
11. def d(list1):
    
12.     return f(list1,len(list1),len(list1[0]))
    

复制代码

flamezyy

1. import itertools
   
2. def f349(grid):
   
3.     last_m = len(grid)
   
4.     last_n = len(grid[0])
   
5.     product = last_m + last_n - 2
   
6.     hor_num = last_n - 1
   
7.     hor_combinations = []
   
8.     result = []
   
9.     for i in itertools.combinations(range(1,product+1),hor_num):
   
10.         hor_combinations.append(i)
    
11.     for p in hor_combinations:
    
12.         i = 0
    
13.         j = 0
    
14.         sum = grid[0][0]  
    
15.         for q in range(1,product+1):
    
16.             if q in p:
    
17.                 j += 1
    
18.                 sum += grid[i][j]
    
19.             else:
    
20.                 i += 1
    
21.                 sum += grid[i][j]        
    
22.         result.append(sum)
    
23.     return max(result)
    

复制代码

估计超时了

塔利班

1. def f349(x):
   
2.     back={(0,0):x[0][0]}
   
3.     I,J=len(x)-1,len(x[0])-1
   
4.     def dp(i,j):
   
5.         if (i,j) in back:
   
6.             return back[(i,j)]
   
7.         else:
   
8.             a=b=0
   
9.             if i>0:
   
10.                 a=dp(i-1,j)+x[i][j]
    
11.             if j>0:
    
12.                 b=dp(i,j-1)+x[i][j]
    
13.             back[(i,j)]=max(a,b)
    
14.             return back[(i,j)]
    
15.     return dp(I,J)

复制代码

TJBEST

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

我这个思路随便用，有可能有更好的。互相交流吧

TJBEST

我个人认为对于函数传入的参数如果是列表等可更改的对象（不可hash的）还是在函数内生成一个备份。我看了大家都是 在传入的列表上面直接更改同时计算 这样原始列表数据也改了，这不符合编程规范。相当于用原始数据计算 同时有更改原始数据。我感觉不太好。

永恒的蓝色梦想

vidyhe 发表于 2020-3-11 14:27
可是没有说每个单元格是多少价格呢

这个格的值就是他的价格