多维数组最短路径问题

题目
给定一个矩阵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]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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])