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

Question

老师看您最新的代码将终点为障碍物的情况已经放在最前面判断了
这样的话我觉得没有必要把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)
}

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

Answer 1

快乐动起来呀 2019-05-23 00:05:29

其实边界都是相对的，我用2，2作为边界就要考虑这个边界要处理的情况，你的思路也没问题的，试试结果，也可以把你的代码放在LeetCode提交下，看看所有的测试用例是否可以跑通

Answer 2

nkliyc 2019-06-28 23:46:40

现在通不过了，会超出时间限制。