329.矩阵中的最长递增路径

链接：329.矩阵中的最长递增路径
难度：Hard
标签：深度优先搜索、广度优先搜索、图、拓扑排序、记忆化搜索、数组、动态规划、矩阵
简介：给定一个整数矩阵，找出最长递增路径的长度。

题解 1 - cpp

• 编辑时间：2021-12-30
• 执行用时：32ms
• 内存消耗：14.3MB
• 编程语言：cpp
• 解法介绍：记忆化 dfs。

class Solution {
   public:
    int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int dfs(int mmap[][200], vector<vector<int>>& matrix, int n, int m, int row,
            int col) {
        if (mmap[row][col]) return mmap[row][col];
        int num = matrix[row][col], ans = 1;
        for (int i = 0; i < 4; i++) {
            int nrow = row + dirs[i][0];
            int ncol = col + dirs[i][1];
            if (nrow < 0 || ncol < 0 || nrow >= n || ncol >= m ||
                matrix[nrow][ncol] <= num)
                continue;
            ans = max(ans, dfs(mmap, matrix, n, m, nrow, ncol) + 1);
        }
        return mmap[row][col] = ans;
    }
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size(), ans = 0, mmap[n][200];
        memset(mmap, 0, sizeof(int) * n * 200);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int tag = 1, num = matrix[i][j];
                for (int k = 0; k < 4; k++) {
                    int nrow = i + dirs[k][0];
                    int ncol = j + dirs[k][1];
                    if (nrow < 0 || ncol < 0 || nrow >= n || ncol >= m)
                        continue;
                    if (matrix[nrow][ncol] < num) {
                        tag = 0;
                        break;
                    }
                }
                if (tag) ans = max(ans, dfs(mmap, matrix, n, m, i, j));
            }
        }
        return ans;
    }
};

题解 2 - typescript

• 编辑时间：2020-07-26
• 执行用时：232ms
• 内存消耗：47.1MB
• 编程语言：typescript
• 解法介绍：记忆化遍历。

function longestIncreasingPath(matrix: number[][]): number {
  const rowLen = matrix.length;
  if (rowLen === 0) return 0;
  const colLen = matrix[0].length;
  const cache = new Map<string, number>();
  const format = (row: number, col: number) => `${row}:${col}`;
  let maxNum = 0;
  const setMax = (num: number) => (maxNum = Math.max(maxNum, num));
  for (let i = 0; i < rowLen; i++) for (let j = 0; j < colLen; j++) setMax(each(i, j));
  return maxNum;
  function each(row: number, col: number, set = new Set<string>()): number {
    const num = matrix[row][col];
    const name = format(row, col);
    if (cache.has(name)) return cache.get(name)!;
    set.add(name);
    let max = 1;
    const setMax = (num: number) => (max = Math.max(max, num));
    if (row !== rowLen - 1 && matrix[row + 1][col] > num && !set.has(format(row + 1, col))) {
      setMax(each(row + 1, col, set) + 1);
    }
    if (row !== 0 && matrix[row - 1][col] > num && !set.has(format(row - 1, col))) {
      max = setMax(each(row - 1, col, set) + 1);
    }
    if (col !== 0 && matrix[row][col - 1] > num && !set.has(format(row, col - 1))) {
      setMax(each(row, col - 1, set) + 1);
    }
    if (col !== colLen - 1 && matrix[row][col + 1] > num && !set.has(format(row, col + 1))) {
      setMax(each(row, col + 1, set) + 1);
    }
    set.delete(name);
    cache.set(name, max);
    return max;
  }
}