This is the 17th day of my participation in the August More text Challenge. For details, see:August is more challenging

Different paths

Title Description: 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 down or to the right at a time. The robot tries to reach the lower right corner of the grid (marked “Finish” in the image below).

How many different paths are there?

For details, see the LeetCode official website.

Source: LeetCode link: leetcode-cn.com/problems/un… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution 1: recursive method

First of all, through the analysis, reach the final step in any one unit grid, could come from the left of the grid, can also be from the top of the grid, so to reach the number of an arbitrary grid is to the left it steps and to its steps of the sum of the grid, so can use recursive method, the specific process is as follows:

  • If m is equal to 1 or n is equal to 1, return 1;
  • If the above conditions are not met, the method is called recursively to solveuniquePaths(m - 1, n) + uniquePaths(m, n - 1).
Solution two: iterative method

First record the first row of the grid number is 1, and then as a result of the first column values are 1, and the following each line 1 ~ n – 1 the value of the column can be according to the current row on the left side of the above a line on the grid and grid value added income, so the value of each line is obtained by iteration, finally return to the last line of the last value is the final result.

public class LeetCode_062 {
    /** * recursion **@param m
     * @param n
     * @return* /
    public static int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) {
            return 1;
        }
        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    }

    /** * Iteration **@param m
     * @param n
     * @return* /
    public static int uniquePaths1(int m, int n) {
        if (m == 1 || n == 1) {
            return 1;
        }
        int[] row = new int[n];
        for (int i = 0; i < n; i++) {
            row[i] = 1;
        }
        for (int i = 2; i <= m; i++) {
            for (int x = 1; x < row.length; x++) {
                row[x] = row[x - 1] + row[x]; }}return row[n - 1];
    }

    public static void main(String[] args) {
        System.out.println(uniquePaths(51.9));
        System.out.println(uniquePaths1(51.9)); }}Copy the code

Give yourself confidence, no one can help you, do not drill into the corner, naturally wide sea and sky!