This is the 21st day of my participation in the August Text Challenge.More challenges in August

The title

A robot is located in the upper left corner of a MMM * NNN grid (the starting point is marked “Start” in the figure below).

The robot can only move one step to the right or down at a time. The robot attempts to reach the lower right corner of the grid (marked “Finish” in the image below).

How many different paths are there?

The sample

Input: m = 3, n = 7 Output: 28 Input: m = 3, n = 2 Output: 3 Description: There are three paths to the lower right corner starting from the upper left corner. Right -> down -> down 2. Down -> Down -> Right 3. Down -> Right -> Down Input: m = 7, n = 3 Output: 28 Input: m = 3, n = 3 Output: 6Copy the code

prompt

  • 1 <= m, n <= 100
  • The data guarantees that the answer is less than or equal to 2 times 10910^9109

Their thinking

According to the limitation that the robot can only move down or right each time, we can get that the source of the current position may be up or left, so we need to calculate the number of paths up and the number of paths on the left to deduce the final result.

Formula: dp [I] [j] = dp [I – 1) [j] + dp [I] [j – 1] dp [I] [j] = dp [j] + [I – 1] dp [I] [1] dp [I] [j] = dp [I – 1) [j] + dp [I] [j] – 1

Code implementation

class Solution { public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; For (int I = 0; i < m; ++i){ dp[i][0] = 1; } for(int i = 1; i < n; ++i){ dp[0][i] = 1; } for(int i = 1; i < m; ++i){ for(int j = 1; j < n; + + j) {/ / the total number to the left of the path above dp [I] [j] = dp [j] + [I - 1] dp [I] [1]; Return dp[m-1][n-1]; }}Copy the code

Complexity analysis

  • Time complexity: O(MN)O(MN)O(MN)
  • Space complexity: O(MN)O(MN)O(MN)

The last

The article has written the bad place, asks the big guys to be generous to give advice, the mistake is the most can let the person grow up, wishes me and the big guy the distance to shorten gradually!

If you feel the article is helpful to you, please click like, favorites, follow, comment four consecutive support, your support is the biggest power of my creation!!

Title source: leetcode-cn.com/problems/un…