漫画：BAT必考题目 （如何压缩状态完成不同路径题目）
不同路径
该题很容易出现在各大厂的面试中，一般会要求手写，所以需要完整掌握。
不同路径：一个机器人位于一个 m x n 网格的左上角，起始点在下图中标记为“Start”。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角，在下图中标记为“Finish”。
问：总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明：m 和 n 的值均不超过 100。
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
02 PART
题目分析
这道题属于相当标准的动态规划，虽然还有一些公式法等其他解法，但是如果面试官问到，基本就是想考察你的动态规划。
拿到题目，首先定义状态。因为有横纵坐标，明显属于二维DP。我们定义DP[i][j]表示到达i行j列的最多路径。同时，因为第0行和第0列都只有一条路径，所以需要初始化为1。
状态转移方程一目了然，dp[i][j] = dp[i-1][j] + dp[i][j-1]。（想象你站在一个十字路口，到达这个十字路口可能的所有路径，就是从东南西北四个方向过来可能出现的所有路径和。放在这道题里，其实就是砍掉东南。）
根据分析，完成代码：
//go
func uniquePaths(m int, n int) int {
dp := make([][]int, m)
for i := 0; i < m; i++ {
dp[i] = make([]int, n)
}
for i := 0; i < m; i++ {
dp[i][0] = 1
}
for j := 0; j < n; j++ {
dp[0][j] = 1
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
return dp[m-1][n-1]
}
（内存不如人意..）
郑重申明（读我的文章必看）：
- 本系列所有教程都不会用到复杂的语言特性，不需要担心没有学过相关语法，使用各语言纯属本人爱好。
- 作为学术文章，虽然风格可以风趣，但严谨，我是认真的。本文所有代码均在leetcode上进行过测试运行。
- 算法思想才是最重要的。
03 PART
代码优化
上面的答案，如果在面试时给出，可以给到7分，后面3分怎么拿，我们真的需要用一个二维数组来存储吗？一起看下！
在上文中，我们使用二维数组记录状态。但是这里观察一下，每一个格子可能的路径，都是由左边的格子和上面的格子的总路径计算而来， 对于之前更早的数据，其实已经用不到了。如下图，计算第三行时，已经用不到第一行的数据了。
那我们只要能定义一个状态，同时可以表示左边的格子和上面的格子，是不是就可以解决问题？所以我们定义状态dp[j]，用来表示当前行到达第j列的最多路径。这个“当前行”三个字很重要，比如我们要计算dp[3]，因为还没有计算出，所以这时dp[3]保存的其实是4（上一行的数据），而dp[2]由于已经计算出了，所以保存的是6（当前行的数据）。理解了这个，就理解如何压缩状态。
最后，根据分析得出代码：
//go
func uniquePaths(m int, n int) int {
dp := make([]int, n)
for j := 0; j < n; j++ {
dp[j] = 1
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
//注意，这里dp[j-1]已经是新一行的数据了，而dp[j]仍然是上一行的数据
dp[j] += dp[j - 1]
}
}
return dp[n-1]
}
