python动态规划求解最短路径问题

动态规划可以很好地解决最短路径问题。具体做法如下：

1. 定义状态：设dp[i][j]表示从起点到(i,j)的最短路径长度。

2. 初始化状态：dp[0][0] = 0，其他dp[i][j] = +∞。

3. 状态转移：对于每个位置(i,j)，考虑从它的上面或左边走过来的情况，取其中较小的一个值加上当前位置的权值，即可得到当前位置的最短路径长度。

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + weight[i][j]

4. 最终状态：dp[m-1][n-1]即为起点到终点的最短路径长度。

Python代码实现如下：

def shortest_path(weight):
    m, n = len(weight), len(weight[0])
    dp = [[float('inf')] * n for _ in range(m)]
    dp[0][0] = weight[0][0]
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + weight[i][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + weight[0][j]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + weight[i][j]
    return dp[m-1][n-1]

其中，weight是一个二维数组，表示每个位置的权值。