题解 | 矩阵的最小路径和

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param matrix int整型二维数组 the matrix
 * @param matrixRowLen int matrix数组行数
 * @param matrixColLen int* matrix数组列数
 * @return int整型
 */
int minPathSum(int** matrix, int matrixRowLen, int* matrixColLen ) {
    // write code here
    int row=matrixRowLen;
    int col=*matrixColLen;
    int dp[row][col];//记录当前位置到出口的最小路径和
    memset(dp,0,sizeof(int)*(row*col));

    //填充dp表最后一列和最后一行,因为只能！向下或向右走
  	//测试用例没有row==1||col==1的情况，我就偷懒了
    dp[row-1][col-1]=matrix[row-1][col-1];

    for(int i=row-2;i>=0;i--){
        dp[i][col-1]=dp[i+1][col-1]+matrix[i][col-1];
    }
    for(int j=col-2;j>=0;j--){
        dp[row-1][j]=dp[row-1][j+1]+matrix[row-1][j];
    }

    //填充剩余dp表
    for(int i=row-2;i>=0;i--){
        for(int j=col-2;j>=0;j--){
            dp[i][j]=matrix[i][j]+(dp[i+1][j]<dp[i][j+1]?dp[i+1][j]:dp[i][j+1]);
        }
    }

    return dp[0][0];
}