本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

一、题目描述

不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例1：

输入：m = 3, n = 7
输出：28
示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28
示例 4：

输入：m = 3, n = 3
输出：6

二、思路分析

• 又是寻址问题，又是问有多少种走法。又是需要你从小到大一步一步解决问题。我都说道这里了如果你还不知道用动态规划来做，我也不知道该咋说了。
• 当然了，解决问题是有很多种的。笔者这里只是建议通过动态规划来解决问题或者说来加强我们对动态规划的熟悉度。并不是说此题非动归不可

转移方程

• 首先，我们考虑下本题是寻找路径的问题，我们直接接触了没有维度的概念，只有执行与方式的不同。但是本体是一个二维维度的问题，所以我们需要借助二维数组来帮我们对小问题的存储。
• 我们首先规定dp[i][j]来表示从地图左上角做到地图(i,j)位置的情况

• 那么我们思考下，如果想在(0,0)位置到大(i，j)位置我们该如果过去呢？题目中也说了我们只能向下或者向右。也就是说我们只能通过增加i或者增加j来进行移动。
• 那么我们换位思考下有哪些点可以通过增加i或者增加j到大(i,j)呢。

• 上面是笔者画的一个图，根据图示应该很明显得出有两个节点可以通过合法的移动到大(i，j) 。
• 也就是存在(i-1,j),(i,j-1)两个节点。到大这两个节点的路径和就是dp[i][j]的值了
• 不知道你有没有发现，如果zxhtom这个机器人走在边缘的话情况就有点特殊了，实际上就是边界问题

• 当机器人走在边界上时，他的来源只能是在轴方向的上一个。因为另外一个是不存在的节点，我们可以理解成此路不通的状态。所以最终我们确定的状态转移方程如下