LeetCode_每日一题今日份_329.矩阵中的最长递增路径(没懂）-蒲公英云

LeetCode_每日一题今日份_329.矩阵中的最长递增路径(没懂）

在这里插入图片描述

const int dirs[4][2] = {
    {
    -1, 0}, {
    1, 0}, {
    0, -1}, {
    0, 1}};
int rows, columns; //定义最终返回的最长递增路劲数组的行、列
int longestIncreasingPath(int** matrix, int matrixSize, int* matrixColSize) {
     //主
    if (matrixSize == 0 || matrixColSize[0] == 0) {
        return 0;
    }
    rows = matrixSize;
    columns = matrixColSize[0];
    int** memo = (int**)malloc(sizeof(int*) * rows); //分配行空间
    for (int i = 0; i < rows; i++) {
        memo[i] = (int*)malloc(sizeof(int) * columns); //分配列空间
        memset(memo[i], 0, sizeof(int) * columns); //分配最终返回的最长递增路劲数组的空间
    }
    int ans = 0;
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < columns; ++j) {
            ans = fmax(ans, dfs(matrix, i, j, memo)); //比较 求出最长递增路径
        }
    }
    free(memo);
    return ans;
}
int dfs(int** matrix, int row, int column, int** memo) {
     //每个单元格的递增路径
    if (memo[row][column] != 0) {
        return memo[row][column];
    }
    ++memo[row][column];
    for (int i = 0; i < 4; ++i) {
        int newRow = row + dirs[i][0], newColumn = column + dirs[i][1];
        if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && matrix[newRow][newColumn] > matrix[row][column]) {
            memo[row][column] = fmax(memo[row][column], dfs(matrix, newRow, newColumn, memo) + 1);
        }
    }
    return memo[row][column];
}