题解 | #矩阵的最小路径和#

#动态规划5部曲—确定dp含义、写出递推公式、初始化、遍历、打印dp（debug）
#确定dp[i][j]含义
#dp[i][j]表示第i行第j列的格子的最小路径和

#写出递推公式
#i行j列只能从i-1行j列或者i行j-1列来
#故：dp[i][j]=min(dp[i-1][j]+cast[i][j],dp[i][j-1]+cast[i][j])

#初始化
#要对所有边界都初始化，对于只能往右和往下，最左边和最上边就是边界，也就是第一行和第一列


n,m=map(int,input().split())
cast=[[int(i) for i in input().split()] for j in range(n)]
# print(cast)
dp=[[0 for i in range(m)] for j in range(n)]

#初始化第一行
for i in range(m):
    for j in range(i+1):
        dp[0][i]+=cast[0][j]

#初始化第一列
for i in range(1,n):
    for j in range(i+1):
        dp[i][0]+=cast[j][0]
# print(dp)

#遍历
for i in range(1,n):
    for j in range(1,m):
        dp[i][j]=min(dp[i-1][j]+cast[i][j],dp[i][j-1]+cast[i][j])
print(dp[n-1][m-1])