本文共 1559 字，大约阅读时间需要 5 分钟。

一个机器人位于一个 m x n 网格的左上角（起点）。它每次只能向下或向右移动一步，目标是到达网格的右下角（终点）。我们需要计算从起点到终点的所有不同路径的数量。

解题思路

我们可以使用动态规划的方法来解决这个问题。动态规划的基本思想是通过将一个大问题分解成多个小问题，分别求解每个小问题，然后将它们的结果结合起来求解大问题。

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

最终，我们需要计算到达终点 (m-1, n-1) 的路径数量，即 f(m-1, n-1)。

代码实现

public class Solution {    public int uniquePaths(int m, int n) {        int[][] ways = new int[m][n];        ways[0][0] = 1; // 起点                // 初始化第一行和第一列        for (int i = 0; i < m; i++) {            ways[i][0] = 1;            if (i == 0) continue; // 第一行不能从二维数组的其他行来            for (int j = 1; j < n; j++) {                ways[i][j] = ways[i - 1][j] + ways[i][j - 1];            }        }                // 初始化第一个行和列        for (int j = 0; j < n; j++) {            if (j == 0) continue; // 第一列不能从二维数组的其他列来            ways[0][j] = 1;        }                // 计算其他行        for (int i = 1; i < m; i++) {            for (int j = 1; j < n; j++) {                ways[i][j] = ways[i - 1][j] + ways[i][j - 1];            }        }                return ways[m-1][n-1];    }}

示例分析

优化思路

为了更高效地计算路径数量，可以使用一维数组来替代二维数组。每次处理当前行时，只使用前一行的数据，这样可以节省内存空间，并提升计算效率。

结论

通过动态规划，我们能够高效地计算从网格左上角到右下角的所有路径数量。代码实现了动态规划的思想，并通过示例验证了其正确性。

转载地址：http://oegyk.baihongyu.com/