# 不同路径

一个机器人位于一个 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

提示：

# 思路分析：动态规划

我们先来分析一下如下格子有几种走法

第一种走法：先向右走一步，再向下走两步

第二种走法：先向下两步，再向右走一步

第三种走法：先向下走一步，再向右走一步，再向下走一步

我们现在知道了 3 行 2 列的格子一共有 3 种走法，那么这三种是怎么来的呢。下面继续拆解

我们先假设格子就这么大，就两个格子大小

那么这时的走法总数只有一种

还有一种情况如下格子是如下这么画的它的走法总数是几？

也是 1，这时它只能向下走，所以也只有一种走法

现在我们把范围扩大到 4 个格子，这时它要走到右下角有几种走法

有 2 种走法，要么它从下面走过来，要么它从上面走过来

这里有个规律这 2 种走法是怎么来的呢，其实就是第一种走法 + 第二种走法 = 2

下面如果格子是这样画的，那么它走到右下角的走法还是 1 种

现在我们把格子范围扩大到整个

那么到达右下角的走法总数就是前两个走法数相加就是 3

规律：右下角它的走法总数就是，右下角它上方的格子的走法数和左方的走法数它们的和就是最终右下角的结果

第一行和第一列它们的走法都是 1 种

	public static void main(String[] args)
	{
	System.out.println(new Demo04().updatePaths(3, 7));
	}

	public int updatePaths(int m, int n)
	{
	// 创建一个 m 行 n 列的二维数组
	int dp[][] = new int[m][n];
	// 第一种走法右边都是 1
	for(int i = 0; i < m; i++)
	{
	dp[i][0] = 1;
	}
	// 第一种走法下边都是 1
	for(int j = 0; j < n; j++)
	{
	dp[0][j] = 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];
	}
	}
	return dp[m - 1][n - 1];
	}