题解 | #矩阵的最小路径和#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param matrix int整型二维数组 the matrix
 * @param matrixRowLen int matrix数组行数
 * @param matrixColLen int* matrix数组列数
 * @return int整型
 */

#define min(a,b) a<b?a:b

int minPathSum(int** matrix, int matrixRowLen, int* matrixColLen ) {
    // write code here
    int** dp = (int**)malloc(sizeof(int*) * matrixRowLen);
    dp[0] = (int*)malloc(sizeof(int) * (*matrixColLen));
    dp[0][0] = matrix[0][0];
    for(int i = 1; i < matrixRowLen; i++) {
        dp[i] = (int*)malloc(sizeof(int) * (*matrixColLen));
        dp[i][0] = matrix[i][0] + dp[i - 1][0];
    }
    for(int i = 1; i < (*matrixColLen); i++) {
        dp[0][i] = matrix[0][i] + dp[0][i - 1];
    }
    for(int i = 1; i < matrixRowLen; i++) {
        for(int j = 1; j < (*matrixColLen); j++) {
            dp[i][j] = min(dp[i - 1][j] + matrix[i][j], dp[i][j - 1] + matrix[i][j]);
        }
    }
    return dp[matrixRowLen - 1][(*matrixColLen) - 1];
}