动态规划路径问题python代码

以下是一个简单的动态规划路径问题的Python代码示例：

def find_path(matrix):
    rows = len(matrix)
    cols = len(matrix[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = matrix[0][0]
    
    # 计算第一行和第一列的路径和
    for i in range(1, rows):
        dp[i][0] = dp[i-1][0] + matrix[i][0]
    for j in range(1, cols):
        dp[0][j] = dp[0][j-1] + matrix[0][j]
        
    # 计算其余位置的路径和
    for i in range(1, rows):
        for j in range(1, cols):
            dp[i][j] = matrix[i][j] + min(dp[i-1][j], dp[i][j-1])
    
    # 回溯路径
    path = [(rows-1, cols-1)]
    i, j = rows-1, cols-1
    while i > 0 or j > 0:
        if i > 0 and dp[i-1][j] < dp[i][j-1]:
            i -= 1
        else:
            j -= 1
        path.append((i, j))
    
    return dp[rows-1][cols-1], path[::-1]

该函数接受一个二维列表`matrix`作为输入，表示一个矩阵，其中每个元素表示从该位置出发到右下角的最小路径和。函数首先创建一个二维列表`dp`，用于存储从左上角到每个位置的最小路径和。然后，函数计算第一行和第一列的路径和，并使用动态规划方法计算其余位置的路径和。最后，函数回溯路径，返回最小路径和以及路径中的坐标列表。