62. Unique Paths

LeetCode

为了便于求解，我们先设左上角起点的坐标为(0, 0)，右下角终点的坐标为(m - 1, n - 1)。接着我们直接从机器人的最后一步为着手点来考察问题。

由于机器人只能向右或者向下走，所以最后一步必然是从(m - 2, n - 1)移动到(m - 1, n - 1)或是从(m - 1, n - 2)移动到(m - 1, n - 1)。换句话来说，为了达到终点，最后一步只有“上 → 下”或者“左 → 右”两种来源。**从最后一步的状态转移，我们可以推导出一个规律：**如果机器人从(0, 0)移动到(m - 2, n - 1)有x种路径，从(0, 0)移动到(m - 1, n - 2)有y种路径，根据加法原理，从(0, 0)移动到(m - 1, n - 1)就有x + y种路径。回头再看原问题：

How many possible unique paths are there? (from to the top-left corner to the bottom-right corner)

上面的步骤相当于把原问题拆分成两个更小的子问题，原问题也就转化为“有多少种方式（路径）从(0, 0)移动到(m - 2, n - 1)和(m - 1, n - 2)”。下面让我们根据题目要求抽象出状态，并根据原问题和子问题的关系，抽象出状态转移方程。

  • f(i, j)：从(0, 0)到(i, j)的路径数
  • f(i, j) = f(i - 1, j) + f(i, j - 1)

然后，我们要考虑初始条件和问题边界：

  • 因为从(0, 0)只有一种方式到达(0, 0)，所以f(0, 0) = 1
  • 因为机器人只能向下走或向右走，所以只要它在第0行或第0列上，它就只有唯一的一条路径可达，故f(i, 0) = 1，f(0, j) = 1
// bottom-up solution
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] f = new int[m][n];
        f[0][0] = 1;
        for (int i = 0; i < m; i++) {
            f[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            f[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }
}