最小路径和

2025/10/16

思路：很明显的动态规划题

D[i][j] = min(D[i-1][j], D[i][j-1]) + a[i][j] D[i][0] = a[0][0] + … + a[i][0] D[0][j] = a[0][0] +… + a[0][j]

在动态规划的时候记录每次取min的哪个

手写代码：

def minPathSum(a, m, n):
    D = [[0] for _ in range(n)] for _ in range(m) 
    path = [[0] for _ in range(n)] for _ in range(m) 

    for i in range(m):
        D[i][0] += a[i][0]
        path[i][0] = "left"
    for j in range(n):
        D[0][j] += a[0][j]
        path[i][0] = "up"

    for i in range(1, m):
        for j in range(1,n):
            if D[i-1][j] <  D[i][j-1]:
                D[i][j] = D[i-1][j]  + a[i][j]
                path[i][j] = "left"
            else: 
                D[i][j] = D[i][j-1]  + a[i][j]
                path[i][j] = "right"
    
    i = m, j= n
    results = [D[m][n]]
    while i != 0 or j = 0:
        if path[i][j] == "left":
            i = i -1
        if path[i][j] == "up":
            j = j -1
        results.append[D[i][j]]
    results = results.reverse()

评价：完全正确，秒了