# Leetcode - unique-paths-ii

violet posted @ Mar 04, 2020 03:35:57 AM in 算法 with tags Algorithm 算法 DP Golang ruby , 595 阅读

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

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as `1` and `0` respectively in the grid.

Note: m and n will be at most 100.

Example 1:

```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
```
10th Model Paper 202 说:
Feb 17, 2023 04:01:33 PM

10th Model Paper 2024 is Get Available by the Board of Secondary Education. The Model Question Paper for class 10th will deliver in online mode on the authority site. The Model Paper will comprise of the subject-wise New Question Paper, day, timings, 10th Model Paper 2024 and significant guidelines for test day. In this article, the up-and-comer will get the data about the 10th Class Latest Question Paper 2024.

model-papers.com 说:
May 02, 2023 07:38:40 PM

Board Model Paper 2023 Aspirants who had Registered for the Maha Board 12th Class Exam can Download the Previous Paper When Board Announces the Dates to Download the Question Paper. model-papers.com Board Question Papers will be Provided Very Soon Through Online Mode and all the Applicants Should Visit the Official Page Regularly for More Information Regarding Previous Paper, Examination Date. Check the Below Provided Details for More Information About the Board Model Paper.

Bihar 3rd Syllabus 说:
Sep 15, 2023 05:26:53 PM

SCERT Bihar 2nd Class Provides the Syllabus for All the This new Syllabus are Designed Strategically by a Team of Subject Experts and are Prescribed by the Bihar State Government, Bihar Primary level Syllabus 2024 for Bihar 3rd Syllabus 2024 the children of Bihar has been developed with the supervision of the Bihar State Textbook Publishing Corporation Ltd, Patna Altogether Seventeen Subjects Syllabus Covering Mathematics, Hindi Language, English as Second Language and Environmental Science have been Prepared, These Syllabus are Freely Distributed under SSA Programme to the Primary Children of Bihar.

(输入验证码)
or Ctrl+Enter