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

ゞ浴缸里的玫瑰 2023-03-01 13:29 14阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 1]

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];
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70]: /images/20230208/14efbc86cee24acb958af9cf6c0cfb6b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 1]: /images/20230208/11296577a5354a2590525a4ff1f48ac9.png