一、题目

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/unique-paths

读者可以先暂停思考一下，看看自己自己有没有解题的思路。

二、思路

2.1 确定算法

首先，我们先选择使用什么算法技巧来求解此题。标题已经写得很明显了，可以使用动态规划，那为什么要使用动态规划呢？
在爬楼梯
中，已经对动态规划算法做过一些介绍，这里不再赘述，我们现在来分析为什么可以使用动态规划来解决此问题。

机器人要从左上角的Start走到右下角Finish的位置，并且只能向下或者向右移动一步。
乍一看，似乎没有什么头绪，因为机器人每一步都有可能向下或者向右走，这样的话就会有非常多的走法，采用暴力枚举并不现实。
机器人达到Finish，必须是从Finish上方一个格子向下走，或者从Finish左方一个格子向右走。
是不是有点眼熟？这就是本题的核心，在爬楼梯那个题目中，张三每次只能走一层或者两层，因此到达第n层时必须达到n-1或者n-2层，这个和本题的思路不谋而合。
总结：机器人后续做的决策都会受到前面所做决策的影响！所以我们可以采用动态规划算法来进行求解

2.2 算法分析

还记得前面说过的动态规划三步骤吗？我们照葫芦画瓢：

2.2.1 定义数组元素含义

我们先来定义一个数组dp[m][n]，它代表机器人走到到第m * n方格所用的方法数，dp[m][n]也就是我们要求的结果。
注：同爬楼梯题目一样，为了方便理解和贴合实际，我们舍弃掉dp[i][0]和dp[0][j]这样的数据，机器人初始位置就是(1，1)，即dp[1][1]。

class Solution {
    /*  省略  */
    int[][] dp = new int[m + 1][n + 1];
    /*  省略  */
}

2.2.2 找出数组元素之间的关系式（状态转移方程）

dp[m][n] = dp[m][n-1] + dp[m-1][n];

2.2.3 找出初始值

这里可能需要稍微理解一下，因为机器人只能向右或者向下走，因此dp[i][1]和dp[1][j]全部都是1，即只有一种到达方法。

class Solution {
    public int climbStairs(int n) {
        /*  省略  */
        for (int i = 1; i <= m; i++) {
            dp[i][1] = 1;
        }
        for (int i = 1; i <= n; i++) {
            dp[1][i] = 1;
        }
        /*  省略  */
    }
}

三、题解

下面就是一个完整的解题算法：

class Solution {
    public int uniquePaths(int m, int n) {
        //到达finish只能是从finish左边那一格向右或上面那一格向下
        //假设d[i][j]表示到达i*j格子的方法数
        //找到关系dp[m][n] = dp[m][n-1]+dp[m-1][n];
        //排除特殊情况
        if (m <= 0 || n <= 0) {
            return 0;
        }
        //定义状态转移方程
        int[][] dp = new int[m + 1][n + 1];
        //设置初始值
        for (int i = 1; i <= m; i++) {
            dp[i][1] = 1;
        }
        for (int i = 1; i <= n; i++) {
            dp[1][i] = 1;
        }
        //运用状态转移方程求出结果
        for (int i = 2; i <= m; i++) {
            for (int j = 2; j <= n; j++) {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }
        return dp[m][n];
    }
}