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

永恒的蓝色梦想

1. class Solution:
   
2.     def maxValue(self, grid: List[List[int]]) -> int:
   
3.         for i in range(len(grid)):
   
4.             for j in range(len(grid[0])):
   
5.                 if not i | j:
   
6.                     pass
   
7.                
   
8.                 elif not i:
   
9.                     grid[i][j] += grid[i][j - 1]
   
10.                     
    
11.                 elif not j:
    
12.                     grid[i][j] += grid[i - 1][j]
    
13.                     
    
14.                 else:
    
15.                     grid[i][j] += (a if (a := grid[i - 1][j]) > (b := grid[i][j - 1]) else b)
    
16. 
    
17.         return grid[-1][-1]

复制代码

动态规划现学现用

ouyunfu

1. def f349(ar:list)->int:
   
2.     def f(L,m,n):
   
3.         if m==1 and n==1:
   
4.             return L[m-1][n-1]
   
5.         if m>1 and n==1:
   
6.             return f(L,m-1,n)+L[m-1][n-1]
   
7.         if m==1 and n>1:
   
8.             return f(L,m,n-1)+L[m-1][n-1]
   
9.         if m>1 and n>1:
   
10.             return max(f(L,m-1,n),f(L,m,n-1))+L[m-1][n-1]
    
11.     x,y=len(ar),len(ar[0])
    
12.     return f(ar,x,y)
    
13. 
    
14. ar=[
    
15.   [1, 3, 1],
    
16.   [1, 5, 1],
    
17.   [4, 2, 1]
    
18. ]
    
19. print(f349(ar))

复制代码

Unicorn#

1. def solve(Map):
   
2.     n = len(Map)
   
3.     m = len(Map[0])
   
4.     Val = []
   
5.     for i in range(n):
   
6.         Val.append([])
   
7.         for j in range(m):
   
8.             Val[i].append(0)
   
9.     Val[0][0] = Map[0][0]
   
10.     for i in range(n):
    
11.         for j in range(m):
    
12.             if i > 0:
    
13.                 a = Val[i-1][j] + Map[i-1][j]
    
14.             else:
    
15.                 a = 0
    
16.             if j > 0:
    
17.                 b = Val[i][j-1] + Map[i][j-1]
    
18.             else:
    
19.                 b = 0
    
20.             if a or b:
    
21.                 Val[i][j] = max(a, b)
    
22.     return Val[n-1][m-1]

复制代码

archlzy

1. def fun349(input_list):
   
2.     m,n = len(input_list[0]),len(input_list)
   
3.     dp = [[0 for _i in range(m)] for _j in range(n)]
   
4.     for i in range(m):
   
5.         for j in range(n):
   
6.             if i == 0 and j == 0:
   
7.                 dp[j][i] = input_list[0][0]
   
8.             elif i == 0:
   
9.                 dp[j][i] = dp[j-1][i] + input_list[j][i]
   
10.             elif j == 0:
    
11.                 dp[j][i] = dp[j][i-1] + input_list[j][i]
    
12.             else:
    
13.                 dp[j][i] = max(dp[j][i-1], dp[j-1][i]) + input_list[j][i]
    
14.     return dp[-1][-1]

复制代码

l0stparadise

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

为啥我看都看不懂。。。。。

l0stparadise

现学了itertools。。。。

1. import itertools
   
2. import numpy as np
   
3. def f349(arr1):
   
4.     lenth=len(arr1)
   
5.     width=len(arr1[0])
   
6.     arr2=np.reshape(arr1,lenth*width)
   
7.     iter_move=(width-1)*str(1)+(lenth-1)*str(width)
   
8.     move_list=set(itertools.permutations(iter_move,lenth+width-2))
   
9.     # print(move_list)
   
10.     count=0
    
11.     init=arr2[0]
    
12.     sum_list=[]
    
13.     for i in move_list:
    
14.         for h in i:
    
15.             count=count+int(h)
    
16.             init += arr2[count]
    
17.         count=0
    
18.         sum_list.append(init)
    
19.         init = arr2[0]
    
20.     return max(sum_list)

复制代码

派生小生

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.     col = line = 1
    
15.     while col < m:
    
16.         while line < n:
    
17.             fuzhu[col][line]=max([fuzhu[col][line-1],fuzhu[col-1][line]])+grid[col][line]
    
18.             line += 1
    
19.         col +=1
    
20.         line = 1
    
21.     return fuzhu[m-1][n-1]

复制代码

派生小生

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

借鉴了大神的思路，然后自己修改了下，思路转变为使用while求出一行行的最大值。

tzczjh

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]

复制代码

永恒的蓝色梦想

l0stparadise 发表于 2020-3-11 22:15
为啥我看都看不懂。。。。。

动态规划

776667

1. from itertools import permutations
   
2. 
   
3. def fun349(grid):
   
4.     path = [0 for i in range(len(grid[0])-1)] + [1 for i in range(len(grid)-1)]
   
5.     max_value = 0
   
6.     for i in permutations(path):
   
7.         position = [0,0]
   
8.         value = grid[0][0]
   
9.         for j in i:
   
10.             if j == 0:
    
11.                 position[0] += 1
    
12.             elif j == 1 :
    
13.                 position[1] += 1
    
14.             value += grid[position[0]][position[1]]
    
15.         if value > max_value:
    
16.             max_value = value
    
17.     return max_value

复制代码

fan1993423

永恒的蓝色梦想 发表于 2020-3-12 08:59
动态规划

动态规划有没有好的资料推荐学习

永恒的蓝色梦想

fan1993423 发表于 2020-3-12 12:16
动态规划有没有好的资料推荐学习

我也只是从网上随便找了篇……不知道小甲鱼有没有

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]]

复制代码