自媒体自助下单网站怎么做,下载关键词推广软件,温州电力建设有限公司网站,奥派电子商务网站建设论文给定一个包含非负整数的 m x n 网格 grid #xff0c;请找出一条从左上角到右下角的路径#xff0c;使得路径上的数字总和为最小。
说明#xff1a;每次只能向下或者向右移动一步示例 1#xff1a;
1 3 1
1 5 1
4 2 1
输入#xff1a;grid [[1,3,1],[1,5,1],[4,2,1]]
输出…
给定一个包含非负整数的 m x n 网格 grid 请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。
说明每次只能向下或者向右移动一步示例 1
1 3 1
1 5 1
4 2 1
输入grid [[1,3,1],[1,5,1],[4,2,1]]
输出7
解释因为路径 1→3→1→1→1 的总和最小。
示例 2
输入grid [[1,2,3],[4,5,6]]
输出12提示
m grid.length
n grid[i].length
1 m, n 200
0 grid[i][j] 200 解题方法【动态规划】 二维数组n * m
递推公式
dp[i][j]表示从Start走到(i,j)位置的最小路径和
dp[i][j] min(dp[i - 1][j] grid[i][j], dp[i][j - 1] grid[i][j])
初始化
dp[0][0] grid[0][0]
第一行元素的最小路径和为从左到右元素和
for i in range(1, n):dp[0][i] dp[0][i - 1] grid[0][i]
第一列元素的最小路径和为从上到下元素和
for j in range(1, m):dp[j][0] dp[j - 1][0] grid[j][0] class Solution:def different_roads(self, graph):# 行数row_number len(nums)# 列数column_number len(graph[0]) if graph[0] else 0 # 默认输入每行的列数都相同for row in graph:if not row:continuecolumn_number max(column_number, len(row)) # 每行的列数不同统计最大的列数dp [[0]* column_number for _ in range(row_number)]dp[0][0] graph[0][0]# 初始化首行for i in range(1, column_number):dp[0][i] dp[0][i -1] graph[0][i]# 初始化首列for j in range(row_number):dp[j][0] dp[j - 1][0] graph[j][0]# 递推公式for i in range(1, row_number):for j in range(1, column_number):dp[i][j] min(dp[i - 1][j] graph[i][j], dp[i][j - 1] graph[i][j])return dp[row_number - 1][column_number - 1]if __name__ __main__:try:nums eval(input())solution Solution()result solution.different_roads(nums)print(result)except Exception as e:print(e) 仅作为代码记录方便自学自查自纠
