leetcode 无法通过

Question

var uniquePathsWithObstacles = function (arr) {
    let m = arr.length // 行数
    let n = arr[0] ? arr[0].length : 0 // 列数
    if (!m || !n) return 0
    let dp = (m, n) => {
        // 检查起始或者目标元素是不是1（被占用了），如果起始或者最后那个格就是1，说明怎么都怎么不到那，直接返回0
        if (arr[m - 1][n - 1] === 1 || arr[0][0] === 1) {
            return 0
        }
        if (m === 2 && n === 2) {
            return (arr[1][1] === 1 || arr[1][0] + arr[0][1] === 2) ? 0 : (arr[1][0] === 1 || arr[0][1] === 1) ? 1 : 2
        } else if (m < 2 || n < 2) {
            if (m < 2) {
                return arr[m - 1].includes(1) ? 0 : 1
            } else {
                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(m, n)
};

老师，我根据你的写法来了，简单的测试都过了，但是上 leetcode 上不能过。

可以帮我看一下是哪里出错了吗？万分感谢老师的帮忙

Answer 1

慕粉1926294646 2020-11-07 18:44:43

提供一个思路：正向思维，遍历表的方式，比如先计算 2*2 的数组，再按 (m-1,n)+(m,n-1) 的方式计算

Answer 2

慕粉1926294646 2020-11-07 17:42:16

嗯，递归的思路在 LeetCode 会超时，等我写完其他思路再分享给你哈