网站建设在线建站,网站qq获取,齐河县城乡建设局官方网站,wordpress管理界面给定一个包含非负整数m*n网格grid#xff0c;请找出一条从左上角到右下角的路径#xff0c;使得路径上的数字总和为最小。 说明#xff1a;每次只能向下或者向右移动一步。 示例1#xff1a; 输入#xff1a;grid [[1,3,1],[1,5,1],[4,2,1]]
输出#xff1a;7
解释… 给定一个包含非负整数m*n网格grid请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。 说明每次只能向下或者向右移动一步。 示例1 输入grid [[1,3,1],[1,5,1],[4,2,1]]
输出7
解释因为路径 1→3→1→1→1 的总和最小。 示例2 输入grid [[1,2,3],[4,5,6]]
输出12 提示 m grid.length
n grid[i].length
1 m, n 200
0 grid[i][j] 200 题解 动态规划 int minPathSum(int** grid, int gridSize, int* gridColSize) {int rows gridSize,columns gridColSize[0];if(rows0 || columns0) return 0;int dp[rows][columns];dp[0][0] grid[0][0];//每行第一个for(int i1;irows;i){dp[i][0]dp[i-1][0]grid[i][0];} //每列第一个for(int j1;jcolumns;j){dp[0][j] dp[0][j-1]grid[0][j];}for(int i1;irows;i){for(int j1;jcolumns;j){dp[i][j]fmin(dp[i-1][j],dp[i][j-1])grid[i][j];}}return dp[rows-1][columns-1]
}
