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

/**
 * 
 * @param matrix int整型二维数组 the matrix
 * @param matrixRowLen int matrix数组行数
 * @param matrixColLen int* matrix数组列数
 * @return int整型
 */

int dfs(int** matrix, int matrixRowLen, int matrixColLen, int **ret, int x, int y) {
    if (x == 0 && y == 0) {
        ret[x][y] = matrix[0][0];
    }

    if (x == 0 && y ==1 ) {
        ret[x][y] = matrix[0][0] + matrix[0][1];
    }

    if (x== 1 && y == 0) {
        ret[x][y] = matrix[0][0] + matrix[1][0];
    }

    if (x - 1 < 0 && y - 1 >= 0) {
        int pre = ret[x][y-1] != 0 ? ret[x][y-1]: dfs(matrix, matrixRowLen, matrixColLen, ret, x, y-1);
        ret[x][y] = pre + matrix[x][y];
    }

    if (x - 1 >= 0 && y -1 < 0) {
        int pre = ret[x -1][y] != 0 ? ret[x-1][y]: dfs(matrix, matrixRowLen, matrixColLen, ret, x-1, y);
        ret[x][y] = pre + matrix[x][y];
    }

    if (x - 1 >= 0 && y -1 >= 0) {
        int f1 = ret[x][y-1] != 0 ? ret[x][y-1]: dfs(matrix, matrixRowLen, matrixColLen, ret, x, y-1);
        int f2 = ret[x -1][y] != 0 ? ret[x-1][y]: dfs(matrix, matrixRowLen, matrixColLen, ret, x-1, y);
        ret[x][y] = fmin(f1,f2) + matrix[x][y];
    } else {
        printf("erro found");
    }
    return ret[x][y];
}


int minPathSum(int** matrix, int matrixRowLen, int* matrixColLen ) {
    int **ret = (int **)malloc(sizeof(int*) * matrixRowLen);
    for (int i = 0; i < matrixRowLen; i++) {
        ret[i] = (int *)malloc(sizeof(int) * matrixColLen[0]);
    }

    for (int i = 0; i < matrixRowLen; i++) {
        for (int j = 0; j < matrixColLen[0]; j++) {
            ret[i][j] = 0;
        }
    }

    return dfs(matrix, matrixRowLen, matrixColLen[0], ret, matrixRowLen -1 , matrixColLen[0] -1);
}