How to solve different path problems in leetcode

Editor to share with you how to solve different path problems in leetcode, I believe most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's go to know it!

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).

How many different paths are there in total?

For example, the image above is a 7 x 3 grid. How many possible paths are there?

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

Example 1:

Input: M = 3, n = 2

Output: 3

Explanation:

Starting from the upper left corner, there are a total of 3 paths to the lower right corner.

1. Right-> right-> Down

two。 Right-> Down-> right

3. Down-> right-> right

Example 2:

Input: M = 7, n = 3

Output: 28

Ideas for solving the problem:

1. This problem can be broken down into a subproblem, and the final result can be obtained by using the result of the subproblem, a typical dynamic programming.

2 the number of paths = step [imai j] + step [imai 1jjj]

3, iMui 1 is used in jMui 1; so in an incremental way

Code

Func uniquePaths (m int, n int) int {step:=make ([] [] int,m) for ipura