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

矩阵的最小路径和

https://www.nowcoder.com/practice/38ae72379d42471db1c537914b06d48e

#动态规划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])

#动态规划#
全部评论

相关推荐

S_Holmes:一想到我苦苦追求的迪子私下里却是985的马子,我的心就在滴血😭😭😭
点赞 评论 收藏
分享
评论
3
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务