Shulou(Shulou.com)06/01 Report--

Editor to share with you how to solve different path problems with golang leetcode dynamic planning. I hope you will get something after reading this article. Let's discuss it together.

A robot is located in the upper-left corner of a m x n grid (the starting point is marked "Start" in the following figure).

The robot can only move down or to the right one step at a time. The robot attempts to reach the lower right corner of the grid (labeled "Finish" in the following image).

Now consider that there are obstacles in the grid. So how many different paths will there be from the upper left corner to the lower right corner?

The obstacles and empty positions in the grid are represented by 1 and 0, respectively.

Note: the values of m and n are not more than 100.

Example 1:

Output: 2 explanation: there is an obstacle right in the middle of the 3x3 grid. There are two different paths from the upper left corner to the lower right corner. Right-> right-> Down-> Down 2. Down-> down-> right-> right

Problem-solving ideas

1. This is a typical dynamic programming problem.

2, sub-problem splitting: because each point can only be from left to right or from top to bottom

The recursive formula is m [I] [j] = m [I-1] [j] + m [I] [jmur1]. Due to the use of iMel 1, j Mel 1 is increasing step by step.

3, if there is a roadblock

M [I] [j] = 0

4. Boundary problem.

If the upper left corner is 1, then m [0] [0] = 0, otherwise 1

5, the top horizontal position can only be from left to right, and the leftmost vertical position can only be from top to bottom

So m [I] [0] = m [I-1] [0], m [0] [j] = m [0] [jmur1]

If there is a roadblock m [I] [0] = 0Perm [0] [j] = 0

Func uniquePathsWithObstacles (obstacleGrid [] [] int) int {if len (obstacleGrid) = = 0 {return 0} m:=make ([] [] int,len (obstacleGrid)) for iRank

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.