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

永恒的蓝色梦想

今天的题目：

编写函数，输入一个矩阵(类型为 List[List[int]])，在只允许向右和向下移动的情况下，输出从左上角到右下角的最小路径和。

示例：

输入：
[
    [131,673,234,103,18],
    [201,96,342,965,150],
    [630,803,746,422,111],
    [537,699,497,121,956],
    [805,732,524,37,331]
]
输出：2427
解释：标红路径即为最短路径

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

xiaosi4081

2020-5-12 20:51:43

1. class Solution:
   
2.     def minPathSum(self, grid):
   
3.         m,n=len(grid),len(grid[0])
   
4.         for _ in range(1,n):grid[0][_]+=grid[0][_-1]  #第一行的路径和
   
5.         for _ in range(1,m):grid[_][0]+=grid[_-1][0]  #第一列的路径和
   
6. 
   
7.         for i in range(1,n):
   
8.             for j in range(1,m):
   
9.                 grid[j][i]+=min(grid[j-1][i],grid[j][i-1])   #然后分别一列一列的求出最短路径和
   
10. 
    
11. 
    
12.         return grid[m-1][n-1]     #最后一个就是求出的最小路径和
    
13. 
    
14. if __name__ == "__main__":
    
15.       obj = Solution()
    
16.        
    
17.       s=[
    
18.          [131,673,234,103,18],
    
19.          [201,96,342,965,150],
    
20.          [630,803,746,422,111],
    
21.          [537,699,497,121,956],
    
22.          [805,732,524,37,331]
    
23.          ]
    
24.       print(obj.minPathSum(s))
    
25. 
    

复制代码

跳转到最佳答案楼层

永恒的蓝色梦想

二楼

参考答案：(结贴后放出)

1. def shortestWay(matrix):
   
2.     for i in range(len(matrix)):
   
3.         for j in range(len(matrix[0])):
   
4.             if i and j:
   
5.                 matrix[i][j]+=min(matrix[i-1][j],matrix[i][j-1])
   
6.             elif i:
   
7.                 matrix[i][j]+=matrix[i-1][j]
   
8.             elif j:
   
9.                 matrix[i][j]+=matrix[i][j-1]
   
10. 
    
11.     return matrix[-1][-1]

复制代码

heidern0612

嗯，你应该设置个只允许作者查看的选项，不然别人解答就都漏出去所有人都能看到了。

永恒的蓝色梦想

heidern0612 发表于 2020-5-12 20:39
嗯，你应该设置个只允许作者查看的选项，不然别人解答就都漏出去所有人都能看到了。

OK

xiaosi4081

1. class Solution:
   
2.     def minPathSum(self, grid):
   
3.         m,n=len(grid),len(grid[0])
   
4.         for _ in range(1,n):grid[0][_]+=grid[0][_-1]  #第一行的路径和
   
5.         for _ in range(1,m):grid[_][0]+=grid[_-1][0]  #第一列的路径和
   
6. 
   
7.         for i in range(1,n):
   
8.             for j in range(1,m):
   
9.                 grid[j][i]+=min(grid[j-1][i],grid[j][i-1])   #然后分别一列一列的求出最短路径和
   
10. 
    
11. 
    
12.         return grid[m-1][n-1]     #最后一个就是求出的最小路径和
    
13. 
    
14. if __name__ == "__main__":
    
15.       obj = Solution()
    
16.        
    
17.       s=[
    
18.          [131,673,234,103,18],
    
19.          [201,96,342,965,150],
    
20.          [630,803,746,422,111],
    
21.          [537,699,497,121,956],
    
22.          [805,732,524,37,331]
    
23.          ]
    
24.       print(obj.minPathSum(s))
    
25. 
    

复制代码

March2615

1. def daily391(grid: list) -> int:
   
2.     if not grid:
   
3.         return 0
   
4.     row, column = len(grid), len(grid[0])
   
5.     dp = [[0] * column for _ in range(row)]
   
6.     dp[0][0] = grid[0][0]
   
7.     for i in range(1, column):
   
8.         dp[0][i] = grid[0][i] + dp[0][i - 1]
   
9.     for i in range(1, row):
   
10.         dp[i][0] = grid[i][0] + dp[i - 1][0]
    
11.         for j in range(1, column):
    
12.             dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
    
13.     pprint(dp)
    
14.     return dp[-1][-1]

复制代码

感觉是不是可以用一维列表就足够了

赚小钱

1. def shortest_path(matrix):
   
2.     dp = [];
   
3.     for i in range(0, len(matrix)):
   
4.         line = [];
   
5.         for j in range(0,len(matrix[i])):
   
6.             line.append(0);
   
7.         dp.append(line);
   
8.     dp[0][0] = matrix[0][0];
   
9.     for i in range(1, len(matrix[0])):
   
10.         dp[0][i] = dp[0][i-1] + matrix[0][i]
    
11.     for i in range(1,len(matrix)):
    
12.         dp[i][0] = dp[i-1][0] + matrix[i][0]
    
13.     for i in range(1, len(matrix)):
    
14.         for j in range(1, len(matrix[i])):
    
15.             if dp[i][j-1] < dp[i-1][j]:
    
16.                 dp[i][j] = dp[i][j-1] + matrix[i][j];
    
17.             else:
    
18.                 dp[i][j] = dp[i-1][j] + matrix[i][j];
    
19.     return dp[len(matrix)-1][len(matrix[0])-1];

复制代码

kinkon

动态规则

1. def f391(List):
   
2.     if not List or not List[0]:
   
3.         return 0
   
4.     m, n = len(List), len(List[0])
   
5.     for i in range(m):
   
6.         for j in range(n):
   
7.             if i == 0 and j == 0:
   
8.                 continue
   
9.             elif i == 0 and j > 0:
   
10.                 List[i][j] += List[i][j-1]
    
11.             elif i > 0 and j == 0:
    
12.                 List[i][j] += List[i-1][j]
    
13.             else:
    
14.                 List[i][j] += min(List[i-1][j], List[i][j-1])                                         
    
15.     #print(List)
    
16.     return List[-1][-1]

复制代码

March2615

1. def daily391_0(grid: list) -> int:
   
2.     if not grid:
   
3.         return 0
   
4.     row, column = len(grid), len(grid[0])
   
5.     steps = [sum(grid[0][:i]) for i in range(1, column + 1)]
   
6.     for i in range(1, row):
   
7.         steps[0] += grid[i][0]
   
8.         for j in range(1, column):
   
9.             steps[j] = min(steps[j - 1], steps[j]) + grid[i][j]
   
10.     return steps[-1]

复制代码

用一维列表保存

塔利班

1. def f391(M):
   
2.     for i in range(len(M)):
   
3.         for j in range(len(M[0])):
   
4.             if i and j:
   
5.                 M[i][j]+=min(M[i-1][j],M[i][j-1])
   
6.             elif i:
   
7.                 M[i][j]+=M[i-1][j]
   
8.             elif j:
   
9.                 M[i][j]+=M[i][j-1]
   
10.     return M[-1][-1]
    

复制代码

rsj0315

这种题涉及的是算法么?

liuzhengyuan

这道题能用贪心解吗？

我打算用动态规划……

风魔孤行者

1. def f(list1):
   
2.     list2 = []
   
3.     for index in range(0,len(list1)):
   
4.         list2.append([0 for i in range(0,len(list1[0]))])
   
5.     list2[0][0] = list1[0][0]
   
6.     for n in range(1,len(list2[0])):
   
7.         list2[0][n] = list2[0][n-1] + list1[0][n]
   
8.     for n in range(1,len(list2)):
   
9.         list2[n][0] = list2[n-1][0] + list1[n][0]
   
10.     for m in range(1,len(list1)):
    
11.         for n in range(1,len(list1[0])):
    
12.             list2[m][n] = min(list2[m-1][n],list2[m][n-1]) + list1[m][n]
    
13.     return list2[-1][-1]

复制代码

好像做过这个题目

Rodrigez10

有答案吗

_2_

rsj0315 发表于 2020-5-12 22:42
这种题涉及的是算法么?

矩阵操作

_2_

这涉及到了我不太擅长的方面（矩阵）
在 leetcode 会含泪跳过

永恒的蓝色梦想

_2_ 发表于 2020-5-13 16:35
这涉及到了我不太擅长的方面（矩阵）
在 leetcode 会含泪跳过

其实就是二维数组

_2_

永恒的蓝色梦想 发表于 2020-5-13 16:38
其实就是二维数组

……
A LeetCode a day keeps confidence away.

ouyunfu

1. def f391(ls):
   
2.     for i in range(len(ls)):
   
3.         for j in range(len(ls[0])):
   
4.             if i!=0 and j==0:
   
5.                 ls[i][j]+=ls[i-1][j]
   
6.             if j!=0 and i==0:
   
7.                 ls[i][j]+=ls[i][j-1]
   
8.             if i!=0 and j!=0:
   
9.                 ls[i][j]+=min(ls[i-1][j],ls[i][j-1])            
   
10.     return ls[-1][-1]

复制代码

zwhe