多维数组最短路径问题

算法

题目
给定一个矩阵m，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，返回所有路径中最小的路径和。
例子：
给定m如下：
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
路径1,3,1,0,6,1,0是所有路径中路径和最小的，所以返回12。

一般这种这种问题可以通过动态规划来解决，因为去年没选算法导论，一直对动态规划这个概念理解不是很清楚

维基百科上的解释为
动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

以往的斐波那契数列和背包问题都是用到动态规划的思想，只是一直知道这就是动态规划而已。

最短路径问题：
设一个数组dp[n][n]，用来存从0，0点到这一点的最短路径和，对于每一点dp[i][j]的值，它等于min(dp[i-1][j], dp[i][j-1]) + arr[i][j]，特别的，dp[0][0] = arr[0][0]，对于第一行，dp[0][j] = dp[0][j - 1] + arr[0][j]对于第一列，dp[i][0] = dp[i-1][0] + arr[i][0]

代码

import sys
arr = sys.stdin.readline().strip().split(" ")
arr = [[int(i) for i in arr]]
num = len(arr[0])
for i in range(num-1):
    new_arr = sys.stdin.readline().strip().split(" ")
    new_arr = [int(i) for i in new_arr]
    arr.append(new_arr)
dp = [[0 for i in range(num)] for i in range(num)]
dp[0][0] = arr[0][0]
for i in range(1,num):
    dp[0][i] = dp[0][i-1] + arr[0][i]
for i in range(1,num):
    dp[i][0] = dp[0][i-1] + arr[0][i]
for i in range(1,num):
    for j in range(1,num):
        dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + arr[i][j]
print(dp[num-1][num-1])