Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
Today, I will continue to do the dynamic programming problem, and continue to start with the intermediate difficulty. I want to put the difficult problems in the later, and when the previous problems are clear, I will start to do the difficult problems.
The title
A robot is located in the upper left corner of an M x N 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?
Example 1:
Input: m = 3, n = 7 Output: 28
Example 2: 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
- Down -> down -> to the right
- Down -> right -> down
Example 3: Input: m = 7, n = 3 Output: 28
Example 4: Input: m = 3, n = 3 Output: 6
Train of thought
Think of it this way: To reach any cell, there are two and only two ways:
- From the left of this cell
- From this lattice over here
Of course, there’s only one case for the leftmost column and the top row. Dp [I][j] = dp[I -1][j] + dp[I][j-1]. Of course, the leftmost column and the top row can be initialized to 1 first. They do not exist on the left or top cell.
Java version code
class Solution { public int uniquePaths(int m, int n) { int dp[][] = new int[m][n]; for (int j = 0; j < n; j++) { dp[0][j] = 1; } for (int i = 1; i < m; i++) { dp[i][0] = 1; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } return dp[m-1][n-1]; }}Copy the code