一个机器人位于一个 m x n 网格的左上角 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径？【LeetCodeHot100】

力扣热题100之62： 

 先贴代码：

class Solution {
    public int uniquePaths(int m, int n) {
        // 创建棋盘
        int[][] board = new int[m][n];
        // 将第0列的格子路径设为1
        for (int i = 0; i < m; i++) {
            board[i][0] = 1;
        }
        // 将第0行的格子路径设为1
        for (int j = 0; j < n; j++) {
            board[0][j] = 1;
        }
        // 往后累加格子的路径数
        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];
    }
}

解题思路：

        题目中告诉我们，需要抵达棋盘的终点（右下角），并且机器人只能一次向右或者向下移动一步，那么当我们抵达一个格子时，只能是从它的左边或者上边过来，由此我们可以推断出：

抵达一个格子的路径数 = 抵达这个格子左边格子的路径数 + 抵达这个格子上边格子的路径数；

即表达式为：                f( i , j ) = f( i - 1 , j ) + f( i , j - 1 )；

        我们先将第0行和第0列的格子全部设为1，表示从起始点走到这些格子有且只有一条路径可以走，我们拿一个 3 * 6 的棋盘举例：

 

        再来开始依次计算剩下空白的格子的路径数，因为由上可知表达式：

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

        所以在求一个格子的路径数时，只要把左边格子 + 上边格子 即可。求得剩下格子路径数为：

 

        由此就可以得出 到达终点的路径数为 15 + 6 = 21 ！