Leetcode - unique-paths-ii

https://leetcode.com/problems/unique-paths-ii/

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

This is another DP.

d[i][j] = d[i-1][j] + d[i][j-1]

func uniquePathsWithObstacles(grid [][]int) int {
    if len(grid) == 0 || len(grid[0]) == 0 {
        return 0
    }    
    r := len(grid)
    c := len(grid[0])
    if grid[r-1][c-1] == 1 {
        return 0
    }
    d := make([][]int, r)
    for i := 0; i < r; i++ {
        d[i] = make([]int, c)
    }

    d[0][0] = 1
    for i := 0; i < r; i++ {
        for j := 0; j < c; j++ {
            if i > 0 && j > 0 {
                if grid[i-1][j] != 1 {
                    d[i][j] += d[i-1][j]
                }
                if grid[i][j-1] != 1 {
                    d[i][j] += d[i][j-1]
                }
            }
            if i == 0 && j != 0 {
                if grid[i][j-1] != 1 {
                    d[i][j] += d[i][j-1]
                }
            }
            if i != 0 && j == 0 {
                if grid[i-1][j] != 1 {
                    d[i][j] += d[i-1][j]
                }
            }
        }
    }
    
    return d[r-1][c-1]
}

# @param {Integer[][]} grid
# @return {Integer}
def unique_paths_with_obstacles(grid)
    return 0 if grid.length == 0 || grid[0].length == 0
    
    dp = Array.new(grid.length){Array.new(grid[0].length, 0)}
    dp[0][0] = 1
    for i in 0..(grid.length - 1) do
        for j in 0..(grid[0].length - 1) do
            if grid[i][j] == 1
                dp[i][j] = 0
                next
            end
            if j > 0 && grid[i][j-1] != 1
                
                dp[i][j] += dp[i][j-1]
            end
            if i > 0 && grid[i-1][j] != 1
                dp[i][j] += dp[i-1][j]
            end
        end
    end
    return dp[grid.length-1][grid[0].length-1]
end

• 相关文章
• 全局相关文章