代码随想录day39【动态规划】不同路径 不同路径2

不同路径

力扣题目链接
简单分析其实不难。

1. dp含义：从（0 ，0）出发，到第i，j位置有几条路径
2. 除了第一列和第一行的元素，只有一条路径。
   其他行列的元素的路径，为左边元素路径及上边元素路径之和。

再根据动规五部曲进行详细分析。

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];
};

改进：
可直接将dp数组初始化为1

不同路径2

力扣题目链接
与上题的区别：

1. 初始化需要修改。第一行或第一列遇到第一个障碍物，后续均初始化为0
2. 递推公式。分情况讨论。有障碍物时，dp[i][j]为0；否则为左边元素路径及上边元素路径之和。

再根据动规五部曲进行详细分析。

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];
};