动态规划解网格最短路径问题_网格最短路径算法动态规划法

问题：

给定一个，包含非负整数的 m x n 网格。请找出一条，从左上角到右下角的路径。使得路径上，所有数字总和为最小，每次只能向下，或者向右移动一步。例如：
输入:
[[1,3,1],
[1,5,1],
[4,2,1]]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

解：
由于路径的方向只能是向下或向右，因此网格的第一行的每个元素只能从左上角元素开始向右移动到达，元素对应的最小路径和等于其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值。由于每个元素对应的最小路径和与其相邻元素对应的最小路径和有关，因此可以使用动态规划求解。
从第二行第二列开始，状态转移方程为：
dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]

def minPathSum(grid) :
    if not grid or not grid[0]:
        return 0
        
    rows, columns = len(grid), len(grid[0])
    dp = [[0] * columns for _ in range(rows)]
    dp[0][0] = grid[0][0]
    #计算第一行的距离
    for i in range(1, rows):
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    #计算第一列的距离
    for j in range(1, columns):
        dp[0][j] = dp[0][j - 1] + grid[0][j]
    #对其余行列进行递归求解
    print('路径距离矩阵为：')
    for i in range(1, rows):
        for j in range(1, columns):
            #找当前解中的最优值来构造最优解
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        print(dp[i-1])
    print(dp[rows-1])
    return dp[rows - 1][columns - 1]

grid = [[1,3,1],[1,5,1],[4,2,1]]
print('\n最短路径距离为',minPathSum(grid))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
'
运行
运行

运行结果：