62. 不同路径

[heyLiup]

62. 不同路径

// 需要初始化一个二维数组，缓存每一个位置的路径和
var uniquePaths = function (m, n) {
  const temp = [[]];
  for (let i = 0; i < n; i++) { 
    temp[i] = [1]
  }
  for (let i = 0; i < m; i++) { 
    temp[0][i] = 1
  }

  for (let i = 1; i < n; i++) {
    for (let j = 1; j < m; j++) {
      temp[i][j] = temp[i - 1][j] + temp[i][j - 1];
    }
  }
  console.log(temp)
  return temp[n - 1][m - 1];
};

63. 不同路径 II

// 在62题解的思路上扩展
var uniquePathsWithObstacles = function (obstacleGrid) {
  const m = obstacleGrid[0].length;
  const n = obstacleGrid.length;
  const temp = [[]];
  let isLeft =false;  //第一栏之中是否有阻碍，有的话后面都是0
  let isTop = false;  //第一列之中是否有阻碍，有的话后面都是0
  for (let i = 0; i < n; i++) {
    temp[i] = isTop ? [0] : [1];
    if (obstacleGrid[i][0] === 1) {
      temp[i] = [0];
      isTop = true;
    }
  }
  for (let i = 0; i < m; i++) {
    temp[0][i] = isLeft ? 0 : 1;
    if (obstacleGrid[0][i] === 1) {
      temp[0][i] = 0;
      isLeft = true;
    }
  }


  for (let i = 1; i < n; i++) {
    for (let j = 1; j < m; j++) {
      if (obstacleGrid[i][j] === 0) {
        temp[i][j] = temp[i - 1][j] + temp[i][j - 1];
      } else {
        temp[i][j] = 0;
      }
    }
  }
  console.log(temp);
  return temp[n - 1][m - 1];
};