The topic of dry

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: 28Copy the code

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 2. Down -> Down -> Right 3. Down -> right -> downCopy the code

Solution: moving gauge

The problem is regular, as shown in the figure below, the total number of routes for each position depends on its previous position and position to the left. Because they tell us explicitly that the robot can only move down and to the right. So we can do a good job of writing out the sorbent recursive equation.

Then we use the five parts of moving gauge to analyze the following:

Dp [I][j] = dp[I][j] = dp[I][j]

2. Summarize the recurrence formula: According to the summarized data, we can get the recurrence formula: F(n) =dp[i-1][j]+dp[I][J-1]

3. How to initialize the dp array: here we need the first row and the first column to be 1 respectively, because their path is on a line, both are 1.

4. Determine the order of traversal: add front to back

Code implementation:

Execution time: 76 ms, beating 92.02% of all JavaScript commits

Memory consumption: 38.4 MB, beating 17.88% of all JavaScript commits

var uniquePaths = function (m, n) {
    let dp = [];
    /* Initialize dp() */
    for (let i = 0; i < m; i++) {
        dp[i] = []
        dp[i][0] = 1
        for (let j = 0; j < n; j++) {
            dp[0][j] = 1}}for (let i = 1; i < m; i++) {
        for (let 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