分析

• 本题的考点：动态规划。

• 状态表示f[i][j]：从起点到达坐标点(i, j)的方案数。

• 状态转移：f[i][j] = f[i-1][j] + f[i][j-1]。另外第一行和第一列上的坐标都只有一种到达的方案。

代码

• C++

class Solution {
public:
    int uniquePaths(int m, int n) {

        vector<vector<int>> f(m, vector<int>(n));
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (!i || !j) f[i][j] = 1;
                else f[i][j] = f[i - 1][j] + f[i][j - 1];
        return f[m - 1][n - 1];
    }
};

• Java

class Solution {
    public int uniquePaths(int m, int n) {

        int[][] f = new int[m][n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (i == 0 || j == 0) f[i][j] = 1;
                else f[i][j] = f[i - 1][j] + f[i][j - 1];
        return f[m - 1][n - 1];
    }
}

时空复杂度分析

• 时间复杂度：$O(n \times m)$，m、n为行数、列数。

• 空间复杂度：$O(n \times m)$。