一道简单的算法题（1）

问题

给定一个二维正数数组，如下。从任意一个点出发，求最长递增长度。假如从下标（0，1），即数字2出发，则最长递增为2-3-4-8-99，长度为5

[
  [1,2,3,4],
  [5,6,7,8],
  [13,4,5,99],
]

解法

求解这题的思想是使用动态规划和深度遍历算法。对于我们所求的一个点，假如我们已经知道从这个点开发，所能走的最大长度，那么就直接返回。如果暂时还没有最大长度，那么就从这个点开始寻找最大的长度。直接看代码。

/**
 * 
 * @param {Array<Array<number>>} data 
 * @param {number} row 
 * @param {number} column 
 */
function findpath(data, row, column) {
  let cache = {}; //缓存已经遍历的点
  let dataRow = data.length;
  let dataColumn = data[0].length;
  function key(row, column) {
    return `${row}${column}`;
  }
  //数组边界验证
  function valide(row, column) {
    if (row < 0 || row >= dataRow) {
      return false;
    }
    if (column < 0 || column >= dataColumn) {
      return false;
    }
    return true;
  }
  // 主方法
  function find(data, row, column) {
    // 如果存在，则直接返回
    if (cache[key(row, column)]) {
      return cache[key(row, column)];
    }
    let v = data[row][column];
    let left = valide(row, column-1) && data[row][column-1] > v ? find(data, row, column-1) : 0;
    let right = valide(row, column+1) && data[row][column+1] > v ? find(data, row, column+1) : 0;
    let top = valide(row - 1, column) && data[row - 1][column] > v ? find(data, row - 1, column) : 0;
    let bottom = valide(row + 1, column) && data[row + 1][column] > v ? find(data, row + 1, column) : 0;
    let max = Math.max(left, top, right, bottom) + 1;
    return max;
  }
  return find(data, row, column);
}