本文共 695 字,大约阅读时间需要 2 分钟。
有一个矩阵map,它每个格子有一个权值。从左上角的格子开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和。返回所有的路径中最小的路径和。给定一个矩阵map及它的行数n和列数m,请返回最小路径和。
给定一个N*M的矩阵,假定N等于4,M等于41 2 3 44 8 3 26 1 4 57 3 7 8现在生成一个大小为N*M的矩阵dp, dp[i][j]的含义为从(0,0)点到(i,j)点的最小路径显然 第一行的路径值就为从0,0点到i,j 每一点值的和1 3 6 10151118 置dp[0][0] = 矩阵值[0][0];对于第一行来说: dp[i][0] = dp[i-1][0] + 矩阵值[i][0];对于第一列来说: dp[0][i] = dp[0][i-1] + 矩阵值[0][i];对于除第一行第一列之后其他的位置有: dp[i][j] = min(dp[i-1][j] ,dp[i][j-1])+ 矩阵值[i][j];至此,状态转移方程求解完毕
class MinimumPath {public: int getMin(vector> juzhen, int n, int m) { vector >dp(n,vector (m,0)); dp[0][0] = juzhen[0][0]; for (int i=1; i
转载地址:http://rehji.baihongyu.com/