Leetcode skimming: dynamic planning 04 (different paths)

62. Different paths

Force button topic link

A robot is in a m x n The top left corner of the grid （ The starting point is marked as “Start” ）.

The robot can only move down or right one step at a time . The robot tries to reach the bottom right corner of the grid （ In the figure below, it is marked as “Finish” ）.

Ask how many different paths there are in total ？

Example 1：

• Input ：m = 3, n = 7
• Output ：28

Example 2：

• Input ：m = 2, n = 3
• Output ：3

explain ： From the top left corner , All in all 3 Path to the bottom right .

1. towards the right -> towards the right -> Down
2. towards the right -> Down -> towards the right
3. Down -> towards the right -> towards the right

Example 3：

• Input ：m = 7, n = 3
• Output ：28

Example 4：

• Input ：m = 3, n = 3
• Output ：6

Tips ：

• 1 <= m, n <= 100
• Question data guarantee that the answer is less than or equal to 2 * 10^9

1. According to the dimension of data , Create a one-dimensional or two-dimensional data area , This is a two-dimensional area , Just make a two-dimensional table
2. Initialize good value , Because the first row and the first column only have one route , So the initialization value is 1
3. analysis dp [i] The meaning of ,dp [ i ] For how many ways to walk in the current position , That is to add up all the walking methods from the left and all the walking methods from the top
4. according to dp[i] How did you get here , Construct assignment equations , That is, the state transition equation

package com.programmercarl.dynamic;

/** * @ClassName UniquePaths * @Descriotion TODO * @Author nitaotao * @Date 2022/7/23 9:13 * @Version 1.0 * https://leetcode.cn/problems/unique-paths/ * 62.  Different paths  **/
public class UniquePaths {
    
    public int uniquePaths(int m, int n) {
    
        /** * dp[ i ]  How many ways to get to this position  */
        int[][] dp = new int[m][n];
        dp[0][0] = 0;
        // Initialize the first line 
        for (int i = 0; i < n; i++) {
    
            dp[0][i] = 1;
        }
        // Initialize the first column 
        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++) {
    
                // The position of each cell is moved from the left grid or the upper grid 
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}