给定一个m行n列的矩阵,从左上角开始每次只能向右或者向下移动,最后到达右下角的位置,路径上的所有数字累加起来作为这条路径的路径和。求所有路径和中最小路径和。
时间: 2023-12-08 21:15:47 浏览: 200
给定一个包含非负整数的M x N网格,请找出一条从左上角到右下角的路径,使得路径的数字总和最小,并显示其路径。
5星 · 资源好评率100%
这是一个经典的动态规划问题,可以使用动态规划来解决。定义一个二维数组dp[m][n],dp[i][j]表示从左上角到(i,j)位置的最小路径和。初始状态为dp[0][0] = matrix[0][0],第一行和第一列的状态为dp[i][0] = dp[i-1][0] + matrix[i][0]和dp[0][j] = dp[0][j-1] + matrix[0][j]。然后递推求解状态方程dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]。最后dp[m-1][n-1]就是从左上角到右下角的最小路径和。
阅读全文