不同路徑

力扣題目鏈接
簡單分析其實不難。

1. dp含義：從（0 ，0）出發(fā)，到第i，j位置有幾條路徑
2. 除了第一列和第一行的元素，只有一條路徑。
   其他行列的元素的路徑，為左邊元素路徑及上邊元素路徑之和。

再根據(jù)動規(guī)五部曲進(jìn)行詳細(xì)分析。

var uniquePaths = function(m, n) {
    let dp = new Array(m).fill(0).map(() => {
        return new Array(n).fill(0);
    });
    for (let i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (let j = 0; j < n; j++) {
        dp[0][j] = 1;
    }

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    return dp[m-1][n-1];
};

改進(jìn)：
可直接將dp數(shù)組初始化為1

不同路徑2

力扣題目鏈接
與上題的區(qū)別：

1. 初始化需要修改。第一行或第一列遇到第一個障礙物，后續(xù)均初始化為0
2. 遞推公式。分情況討論。有障礙物時，dp[i][j]為0；否則為左邊元素路徑及上邊元素路徑之和。

再根據(jù)動規(guī)五部曲進(jìn)行詳細(xì)分析。

var uniquePathsWithObstacles = function(obstacleGrid) {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
    let dp = new Array(m).fill(0).map(() => {
        return new Array(n).fill(1);
    });

  // 初始化
  for (let i = 0; i < m; i++) {
    if (obstacleGrid[i][0] > 0) {
      //遇到第一個障礙物，后面的均初始化為0
      while (i < m) {
        dp[i][0] = 0;
        i++;
      }
      break;
    }
  }
  for (let j = 0; j < n; j++) {
    if (obstacleGrid[0][j] > 0) {
      while (j < n) {
        dp[0][j] = 0;
        j++;
      }
      break;
    }
  }

  // 求值
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      // 有障礙物
      if (obstacleGrid[i][j] > 0) {
        dp[i][j] = 0;
      } else {//無障礙物
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      }
    }
  }

  return dp[m - 1][n - 1];
};