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

Force deduction hot question 100 And 62： 

  Post the code first ：

class Solution {
    public int uniquePaths(int m, int n) {
        //  Create a chessboard 
        int[][] board = new int[m][n];
        //  Will be the first 0 The grid path of the column is set to 1
        for (int i = 0; i < m; i++) {
            board[i][0] = 1;
        }
        //  Will be the first 0 The grid path of the row is set to 1
        for (int j = 0; j < n; j++) {
            board[0][j] = 1;
        }
        //  Accumulate the number of paths in the grid 
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                board[i][j] = board[i-1][j] + board[i][j-1];
            }
        }
        return board[m-1][n-1];
    }
}

Their thinking ：

        The title tells us , You need to reach the end of the chessboard （ The lower right corner ）, And the robot can only move right or down one step at a time , So when we reach a grid , It can only come from its left or top , From this we can infer that ：

The number of paths to a grid =  The number of paths to the left of this grid + The number of paths to the upper grid of this grid ;

That is, the expression is ：                f( i , j ) = f( i - 1 , j ) + f( i , j - 1 );

        Let's start with the 0 Xing He 0 The cells of the column are all set to 1, It means that there is only one path from the starting point to these grids , Let's take one 3 * 6 Example of chessboard ：

 

         Then start to calculate the number of paths of the remaining blank grids in turn , Because the expression is known from the above ：

                                                f( i , j ) = f( i - 1 , j ) + f( i , j - 1 );

        So when finding the number of paths in a lattice , Just put the left pane + Upper grid that will do . Find that the number of paths in the remaining lattice is ：

 

        It can be concluded that The number of paths to the destination is 15 + 6 = 21 ！