题干： 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例: 输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。解题思路： | 1 | 2 | | 3 | 4 | 以该矩阵为例，若想知道该矩阵到4的最小路径，其实只需要对比2，3哪个更小即可，选择小的那边，因此可以使用动态规划。 动态规划的三步： 1.状态定义： 假设dp[ i ][ j ]表示到达矩阵（i, j）处，最短路径的值。 2.状态转移方程： 对于（i, j）他的路径只能从（i - 1, j）和（i, j - 1）两个地方到来。因此，状态转移方程为： dp[ i ][ j ] = max(dp[ i - 1 ][ j ], dp[ i ][ j - 1]) + grid[ i ][ j ] 3.边界条件： i == 0 && j == 0时，dp[ 0 ][ 0 ] = grid[ 0 ][ 0 ]; i == 0 && j > 0时，dp[ i ][ j ] = dp[ 0 ][ j - 1] + grid[ i ][ j ] ; i > 0 && j == 0时，dp[ i ][ j ] = dp[ i - 1 ][ 0 ] + grid[ i ][ j ];
代码实现：
int minPathSum(int** grid, int gridSize, int* gridColSize) { int i, j; int** dp = (int**)malloc(sizeof(int*) * gridSize); for (int a = 0; a < gridSize; a++) { dp[a] = (int*)malloc(sizeof(int) * gridColSize[a]); } dp[0][0] = grid[0][0]; for (i = 1; i < gridSize; i++) { dp[i][0] = dp[i - 1][0] + grid[i][0]; } for (j = 1; j < (* gridColSize); j++) { dp[0][j] = dp[0][j - 1] + grid[0][j]; } for (i = 1; i < gridSize; i++) { for (j = 1; j < (* gridColSize); j++) { dp[i][j] = (dp[i - 1][j] < dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1]) + grid[i][j]; } } return dp[i - 1][j - 1]; }