本文主要是介绍一个机器人位于一个 m x n 网格的左上角 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径?【LeetCodeHot100】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
力扣热题100之62:
先贴代码:
class Solution {public int uniquePaths(int m, int n) {// 创建棋盘int[][] board = new int[m][n];// 将第0列的格子路径设为1for (int i = 0; i < m; i++) {board[i][0] = 1;}// 将第0行的格子路径设为1for (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 !
这篇关于一个机器人位于一个 m x n 网格的左上角 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径?【LeetCodeHot100】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!