Leetcode - unique-paths-ii
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]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | 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]} |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | # @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 |
2 年前
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.
大约 1 年前
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.
大约 1 年前
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.