本文共 709 字，大约阅读时间需要 2 分钟。

思路：

用动态规划的话，速度是最快的。

状态迁移方程：mat[i][j] = (mat[i][j + 1]<mat[i + 1][j] ? mat[i][j + 1] : mat[i + 1][j]) + grid[i][j];

即要找到一个格子的下边和右边较小的值，在加上grid中给他的值，作为mat中这个位置的最终值。

int minPathSum(vector
   
    
     >& grid) {	int m = grid.size();	if (m == 0){		return 0;	}	int n = grid[0].size();	int** mat = new int*[m]();	for (int i = 0; i < m; i++){		mat[i] = new int[n]();	}	mat[m - 1][n - 1] = grid[m-1][n-1];	for (int i = m - 1; i >= 0; i--){		for (int j = n - 1; j >= 0; j--){			if (i == m - 1 && j == n - 1){				continue;			}			if (j == n - 1){				mat[i][j] = mat[i + 1][j] + grid[i][j];//最底最右的边，等于自身值加前空的值			}			else if (i == m - 1){				mat[i][j] = mat[i][j + 1] + grid[i][j];			}			else{				mat[i][j] = (mat[i][j + 1]