Hello, I’m Dabin

Today I would like to share with you a Tencent interview algorithm question (LeetCode62), the National Day holiday together charge ~

The title

A robot is located in the upper left corner of an M x N grid. The robot can only move one step to the right or down at a time. The robot tries to reach the lower right corner of the grid.

How many different paths are there?

Example:

Input: m = 3, n = 2

Output: 3

Starting at the top left, there are three paths to the bottom right.

1. Right -> down -> down
2. Down -> down -> to the right
3. Down -> right -> down

Source: LeetCode//leetcode-cn.com/problems/unique-pathsCopyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Their thinking

So let’s start with the idea of dynamic programming.

Dynamic programming is used to deal with problems with overlapping subproblems. Its basic idea: if want to solve a problem, need to decompose the problem into sub-problem first, work out the solution of the sub-problem, then according to the solution of the sub-problem get the solution of the original problem.

The dynamic programming algorithm will store the solution of the calculated subproblem, so that the solution of the subproblem can be directly obtained when the same subproblem is encountered next time, reducing the repeated calculation.

Solution ideas of dynamic programming: 1. State definition; 2. State transition equation; 3. Initial state; 4. Determine the traversal order.

Next, explain the idea of this topic step by step.

1. First, state definition. Let dp[I][j] be the number of paths to (I, j), and dp[2][2] be the number of paths to (2, 2).

2. Then there is the state transition equation. Dp [I][j] = dp[I][j] = dp[I][j] + dp[I][J-1]

3. Initial state. For the first row dp[0][j] and the first column dp[I][0], since both are on the boundary, there is only one direction to go, so it can only be 1.

4. Determine the traversal order. Dp [I][j] is derived from above and to the left, so it is traversed from left to right and top to bottom.

Code implementation

Use the two-dimensional array dp[][] to save the intermediate state, and the time complexity and space complexity are O(m*n).

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    / / initialization
    for (int i = 0; i < n; i++) {
        dp[0][i] = 1;
    }
    / / initialization
    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            // Equation of state
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; }}return dp[m - 1][n - 1];
}
Copy the code

Optimization 1: according to the state transition equation DP [I][j] = DP [i-1][j] + DP [I][J-1], only the data of the current row and the previous row need to be saved, and the spatial complexity can be optimized to O(2n). The specific code is as follows:

public int uniquePaths(int m, int n) {
    int[] preRow = new int[n];
    int[] curRow = new int[n];
    / / initialization
    for (int i = 0; i < n; i++) {
        preRow[i] = 1;
        curRow[i] = 1;
    }
    for (int i = 1; i < m; i++){
        for (int j = 1; j < n; j++){
            curRow[j] = curRow[j-1] + preRow[j];
        }
        preRow = curRow.clone();
    }
    return curRow[n-1];
}
Copy the code

Optimization of 2: PreRow [j] = preRow[j] = preRow[j] = preRow[j] = preRow[j] = preRow[j] = preRow[j] = preRow[j] = preRow[j] = preRow[j] = preRow[j] = preRow[j] = preRow[j] = preRow[j] = preRow[j] = preRow[j] = preRow[j] = preRow[j] = preRow[j] [j] = preRow[j] = preRow[j] = preRow[j] = preRow[j] = preRow[j] = preRow[j] = preRow[j] = preRow[j] = preRow[j] = preRow[j] Just use the curRow array as follows:

public int uniquePaths(int m, int n) {
    int[] curRow = new int[n];
    / / initialization
    for (int i = 0; i < n; i++) {
        curRow[i] = 1;
    }
    for (int i = 1; i < m; i++){
        for (int j = 1; j < n; j++){
            curRow[j] += curRow[j-1]; }}return curRow[n-1];
}
Copy the code

This Tencent interview question is a relatively simple topic in dynamic planning. Although it is not difficult, it is still a little difficult to bug free and achieve the optimal solution in the tense atmosphere of the interview.

I hope you can learn something from this book. If you have a better solution, please discuss it together