這是什麼

記憶法，意味著演算法在執行過程當中，隨時儲存計算過的數值。

Memoization 是 Dynamic Programming 的前置作業，趁現在刷一題相關題目來了解其中的含意。

刷題：329. Longest Increasing Path in a Matrix

題目

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

Input: nums =
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: nums =
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

思考

找尋找長路徑，可以使用 DFS 探索每個可能選項。探索完成後再建立一個變數負責儲存結果。

解題

JS

/**
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @param {number} d
 */
const max = (a, b, c, d) => {
  let maxValue = 0;

  if (a > maxValue) {
    maxValue = a;
  }

  if (b > maxValue) {
    maxValue = b;
  }

  if (c > maxValue) {
    maxValue = c;
  }

  if (d > maxValue) {
    maxValue = d;
  }

  return maxValue;
};

/**
 * @param {number} prev
 * @param {number[][]} matrix
 * @param {number} row
 * @param {number} col
 * @param {number[][]} walkedLength
 */
const dfs = (prev, matrix, row, col, walkedLength) => {
  if (row < 0 || row >= matrix.length || col < 0 || col >= matrix[0].length || matrix[row][col] <= prev) {
    return 0;
  }

  if (walkedLength[row][col] !== 0) {
    return walkedLength[row][col];
  }

  let left = dfs(matrix[row][col], matrix, row, col - 1, walkedLength) + 1;
  let right = dfs(matrix[row][col], matrix, row, col + 1, walkedLength) + 1;
  let up = dfs(matrix[row][col], matrix, row - 1, col, walkedLength) + 1;
  let down = dfs(matrix[row][col], matrix, row + 1, col, walkedLength) + 1;
  walkedLength[row][col] = max(left, right, up, down);

  return walkedLength[row][col];
};

/**
 * @param {number[][]} matrix
 * @return {number}
 */
const longestIncreasingPath = (matrix) => {
  if (matrix === null || matrix.length === 0 || matrix[0].length === 0) {
    return 0;
  }

  let rows = matrix.length;
  let cols = matrix[0].length;
  let walkedLength = new Array(rows).fill([]).map(() => new Array(cols).fill(0));

  let longest = 0;

  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (walkedLength[row][col] === 0) {
        let maxLength = dfs(-1, matrix, row, col, walkedLength);

        if (maxLength > longest) {
          longest = maxLength;
        }
      }
    }
  }

  return longest;
};

Java

class Solution {
    public int max(int a, int b, int c, int d) {
        int maxValue = 0;

        if (a > maxValue) {
            maxValue = a;
        }

        if (b > maxValue) {
            maxValue = b;
        }

        if (c > maxValue) {
            maxValue = c;
        }

        if (d > maxValue) {
            maxValue = d;
        }

        return maxValue;
    }

    public int dfs(int prev, int[][] matrix, int row, int col, int [][]walkedLength) {
        if (row < 0 || row >= matrix.length || col < 0 || col >= matrix[0].length || matrix[row][col] <= prev) {
            return 0;
        }

        if (walkedLength[row][col] != 0) {
            return walkedLength[row][col];
        }

        int left = dfs(matrix[row][col], matrix, row, col - 1, walkedLength);
        int right = dfs(matrix[row][col], matrix, row, col + 1, walkedLength);
        int up = dfs(matrix[row][col], matrix, row - 1, col, walkedLength);
        int down = dfs(matrix[row][col], matrix, row + 1, col, walkedLength);
        walkedLength[row][col] = max(left, right, up, down);

        return walkedLength[row][col];
    }

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] walkedLength = new int[rows][cols];
        int longest = 0;

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (walkedLength[row][col] == 0) {
                    int maxLength = dfs(Integer.MIN_VALUE, matrix, row, col, walkedLength);

                    if (maxLength > longest) {
                        longest = maxLength;
                    }
                }
            }
        }

        return longest;
    }
}

C

int max(int a, int b, int c, int d)
{
    int maxValue = 0;

    if (a > maxValue)
    {
        maxValue = a;
    }

    if (b > maxValue)
    {
        maxValue = b;
    }

    if (c > maxValue)
    {
        maxValue = c;
    }

    if (d > maxValue)
    {
        maxValue = d;
    }

    return maxValue;
}

int dfs(int prev, int **matrix, int rowSize, int colSize, int row, int col, int **walkedLength)
{
    if (row < 0 || row >= rowSize || col < 0 || col >= colSize || matrix[row][col] <= prev)
    {
        return 0;
    }

    if (walkedLength[row][col] != 0)
    {
        return walkedLength[row][col];
    }

    int left = dfs(matrix[row][col], matrix, rowSize, colSize, row - 1, col, walkedLength) + 1;
    int right = dfs(matrix[row][col], matrix, rowSize, colSize, row + 1, col, walkedLength) + 1;
    int up = dfs(matrix[row][col], matrix, rowSize, colSize, row, col - 1, walkedLength) + 1;
    int down = dfs(matrix[row][col], matrix, rowSize, colSize, row, col + 1, walkedLength) + 1;
    walkedLength[row][col] = max(left, right, up, down);

    return walkedLength[row][col];
}

int longestIncreasingPath(int **matrix, int matrixSize, int *matrixColSize)
{
    if (!matrix || !matrixSize || !matrixColSize)
    {
        return 0;
    }

    int **walkedLength = malloc(matrixSize * sizeof(int *));

    for (int i = 0; i < matrixSize; ++i)
    {
        walkedLength[i] = calloc(*matrixColSize, sizeof(int));
    }

    int longest = 0;

    for (int row = 0; row < matrixSize; row++)
    {
        for (int col = 0; col < *matrixColSize; col++)
        {
            if (walkedLength[row][col] == 0)
            {
                int maxLength = dfs(INT_MIN, matrix, matrixSize, *matrixColSize, row, col, walkedLength);

                if (maxLength > longest)
                {
                    longest = maxLength;
                }
            }
        }
    }

    free(walkedLength);
    return longest;
}

看法

先談論 Java 與 JS，這邊可以充分體會到 JS 的異步的特色，在於製作四個方向的結果（left、right、up、down），Java 會一個一個執行，JS 反倒不會。因此，再起始值以及每個方向的結果都有做修改，好跑出正確的結果。

C 的部份難產中，calloc、malloc 我有點混亂...
搞懂了，沒注意到 matrixColSize 前面有個 *，帶錯導致錯誤：addresssanitizer requested allocation size 產生。

結論

與其說是練習 Memoization，倒不如說是搭配演算法，好減少執行的時間。
同時，加深 C 的練習，因為有 pointer 存在，函式帶入任一參數時要比 JS 與 Java 更加小心。