老师我觉得只有两种边界情况

来源：14-2 不同路径II-代码实操

一只小小小小白

2019-05-21

老师看您最新的代码将终点为障碍物的情况已经放在最前面判断了
这样的话我觉得没有必要把F(2，2)单独作为一种边界情况了,他继续向下拆分依然可以拆分为F(1，2)+F(2，1),而这两种就是一行和一列的边界，所有的路径最后都可以拆分成1行或一列。
这是修改过的代码

export default arr => {
  let dp = (m, n) => {
    if (arr[m - 1][n - 1] === 1 || arr[0][0] === 1) {
      return 0
    }
    if (m < 2 || n < 2) {
      // 第一种边界 1行n列
      if (m < 2) {
        return arr[m - 1].includes(1) ? 0 : 1
      } else {
        // 第二种边界 n行1列
        for (let i = 0; i < m; i++) {
          if (arr[i][0] === 1) {
            return 0
          }
        }
        return 1
      }
    } else {
      // 递归
      return dp(m - 1, n) + dp(m, n - 1)
    }
  }
  return dp(arr.length, arr[0].length)
}

您的用例是都可以通过的。

写回答

2回答