LC62. 不同路径

题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？ I5Aab7QCjoatk4xqriOcIEzCnHf.png

题目解析

题目在说什么

想象有一个 m 行 n 列的棋盘，机器人站在左上角那个格子里，它想走到右下角的格子。它每次只能走一步，而且只能往右走或者往下走，不能往上或往左。我们要算一算，从起点到终点，总共有多少种不同的走法。

比如一个 2 行 3 列的网格，你可以试着画一画：从左上角到右下角，先右再右再下，或者先下再右再右，或者先右再下再右……数一数，总共 3 种。题目就是让你用程序算出这个数字，不管网格多大。

思路是怎么来的

你可能会想：这题能不能一个一个枚举所有路径？但 m 和 n 稍微大一点，比如 10×10，路径数量就爆炸了，计算机也枚举不过来。所以我们需要一个更聪明的办法。

生活化比喻：假设你是一个快递员，要从公司（起点）送快递到客户家（终点），你只能向右或向下走。你想知道有多少条不同的路线。你发现一个规律：要到达某个路口，你只能从它左边的路口走过来，或者从它上边的路口走下来。所以，到达这个路口的路线数，就等于到达左边路口的路线数加上到达上边路口的路线数。

这个规律就是动态规划的核心思想：把一个大问题拆成小问题，小问题的答案可以一步步推出大问题的答案。

具体到这个题：

• 我们用一个表格（二维数组）来记录到达每个格子有多少种走法。
• 表格里每个格子的数字，等于它左边格子的数字加上它上面格子的数字。
• 起点格子只有 1 种走法（就是站在原地不动）。
• 第一行和第一列的格子，因为只能一直向右或一直向下，所以也都只有 1 种走法。
• 然后我们按照这个规则，把整个表格填满，右下角那个格子的数字就是答案。

代码逐步拆解

我们来看参考代码，一行一行解释它在做什么。

int[][] dp = new int[m][n];

这行创建了一个 m 行 n 列的二维数组，名字叫 dp。dp[i][j] 就表示从起点走到第 i 行第 j 列的格子有多少种不同的路径。注意，行和列都是从 0 开始数的，所以起点是 dp[0][0]，终点是 dp[m-1][n-1]。

dp[0][0] = 1;

起点只有 1 种走法：就是不动。所以赋值为 1。

for(int i = 1; i < m ; i++){
    dp[i][0] = 1;
}

这个循环处理第一列（第 0 列）的所有格子。因为机器人只能向右或向下，要到达第一列的某个格子（比如第 2 行第 0 列），只能一直向下走，没有其他选择，所以路径数只有 1 种。所以把第一列所有格子都设为 1。

for(int j = 1; j < n ; j++){
    dp[0][j] = 1;
}

同理，第一行（第 0 行）的所有格子，只能一直向右走，所以也都只有 1 种路径。

for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
        dp[i][j] = dp[i-1][j] + dp[i][j-1];
    }