编辑代码

/** 
    1、确定dp数组（dp table）以及下标的含义
    2、确定递推公式
    3、dp数组如何初始化
    4、确定遍历顺序
    5、举例推导dp数组

    一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
    机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
    问总共有多少条不同的路径？
    [
        [o,0,0],
        [0,1,0],
        [0,0,o]
    ]

    1、dp[i-1][j-1]表示 i * j 的表格从左上角到右下角的路线种数
    2、dp[i-1][j-1] = dp[i-2][j-1] + dp[i-1][j-2]
    3、 dp = 
    [
        [1,1,1],
        [1,0,1],
        [1,1,2]
    ]
    4、从左上到右下
    5、同3
*/
function main(table) {
    const m = table.length
    const n = table[0].length
    if(table[m-1][n-1] === 1 || table[0][0] === 1) return 0
    // console.log(m, ' - ', n)
    let dp = []
    for(let i =1; i<=m; i++){
        dp.push([])
    }
    let place = []
    function isPlactNext(type, i, j) {
        if(place.length === 0) return false
        let flag = false
        place.some(item=>{
            if(type === 'i' && i === item[0] && j === item[1] + 1) {
                flag = true
                return true
            } else if(type === 'j' && j === item[1] && i === item[0] + 1) {
                flag = true
                return true
            }
        })
        return flag
    }
    for(let i=0; i<=m-1; i++){
        for(let j=0; j<=n-1; j++){
            if(table[i][j] === 1) {
                place.push([i, j])
                dp[i][j] = 0
            } else if(isPlactNext('i', i, j)) {
                if(i === 0) {
                    dp[i][j] = 0
                } else if(table[i-1][j] === 1) {
                    dp[i][j] = 0
                } else {
                    dp[i][j] = dp[i-1][j]
                }
            } else if(isPlactNext('j', i, j)) {
                if(j === 0) {
                    dp[i][j] = 0
                } else if(table[i][j-1] === 1) {
                    dp[i][j] = 0
                } else {
                    dp[i][j] = dp[i][j-1]
                }
            } else if(i === 0) {
                dp[i][j] = j>0 ? dp[i][j-1] : 1
            } else if(j === 0) {
                dp[i][j] = i>0 ? dp[i-1][j] : 1
            } else {
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            }

        }
    }
    console.log('table',table)
    console.log('dp',dp)
    return dp[m-1][n-1]
}
// const result = main([
//         [0,0,0],
//         [0,1,0],
//         [0,0,0]
//     ])
const result = main([[0,1,0,0,0],[1,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]])
console.log('result:',result)
// 时间复杂度：O(m*n)
// 空间复杂度：O(m*n)





function main2(table) {
    const m = table.length
    const n = table[0].length
    const dp = Array(m).fill().map(item => Array(n).fill(0))
    
    for (let i = 0; i < m && table[i][0] === 0; ++i) {
        dp[i][0] = 1
    }
    
    for (let i = 0; i < n && table[0][i] === 0; ++i) {
        dp[0][i] = 1
    }
    
    for (let i = 1; i < m; ++i) {
        for (let j = 1; j < n; ++j) {
            dp[i][j] = table[i][j] === 1 ? 0 : dp[i - 1][j] + dp[i][j - 1]
        }
    }
        
    return dp[m - 1][n - 1]
}
console.log(main2([[0,1,0,0,0],[1,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]))
// 时间复杂度：O(m*n)
// 空间复杂度：O(m*n)