漫画：BAT必考题目 （如何压缩状态完成不同路径题目）
今天是小浩算法“365刷题计划”第51天。为大家分享一道BAT常考题目，不同路径。
01PART不同路径
该题很容易出现在各大厂的面试中，一般会要求手写，所以需要完整掌握。
不同路径：一个机器人位于一个 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
（瞪一瞪就全部掌握）
02PART题目分析
这道题属于相当标准的动态规划，虽然还有一些公式法等其他解法，但是如果面试官问到，基本就是想考察你的动态规划。
拿到题目，首先定义状态。因为有横纵坐标，明显属于二维DP。我们定义DP[i][j]表示到达i行j列的最多路径。同时，因为第0行和第0列都只有一条路径，所以需要初始化为1。
状态转移方程一目了然，dp[i][j] = dp[i-1][j] + dp[i][j-1]。（想象你站在一个十字路口，到达这个十字路口可能的所有路径，就是从东南西北四个方向过来可能出现的所有路径和。放在这道题里，其实就是砍掉东南。）
1//go
2func uniquePaths(m int, n int) int {
3 dp := make([][]int, m)
4 for i := 0; i < m; i++ {
5 dp[i] = make([]int, n)
6 }
7 for i := 0; i < m; i++ {
8 dp[i][0] = 1
9 }
10 for j := 0; j < n; j++ {
11 dp[0][j] = 1
12 }
13 for i := 1; i < m; i++ {
14 for j := 1; j < n; j++ {
15 dp[i][j] = dp[i-1][j] + dp[i][j-1]
16 }
17 }
18 return dp[m-1][n-1]
19}
（内存不如人意..）
郑重申明（读我的文章必看）：
本系列所有教程都不会用到复杂的语言特性，不需要担心没有学过相关语法，使用各语言纯属本人爱好。
作为学术文章，虽然风格可以风趣，但严谨，我是认真的。本文所有代码均在leetcode上进行过测试运行。
算法思想才是最重要的。
03PART代码优化
上面的答案，如果在面试时给出，可以给到7分，后面3分怎么拿，我们真的需要用一个二维数组来存储吗？一起看下！
在上文中，我们使用二维数组记录状态。但是这里观察一下，每一个格子可能的路径，都是由左边的格子和上面的格子的总路径计算而来， 对于之前更早的数据，其实已经用不到了。如下图，计算第三行时，已经用不到第一行的数据了。
那我们只要能定义一个状态，同时可以表示左边的格子和上面的格子，是不是就可以解决问题？所以我们定义状态dp[j]，用来表示当前行到达第j列的最多路径。这个“当前行”三个字很重要，比如我们要计算dp[3]，因为还没有计算出，所以这时dp[3]保存的其实是4（上一行的数据），而dp[2]由于已经计算出了，所以保存的是6（当前行的数据）。理解了这个，就理解如何压缩状态。
最后，根据分析得出代码：
1//go
2func uniquePaths(m int, n int) int {
3 dp := make([]int, n)
4 for j := 0; j < n; j++ {
5 dp[j] = 1
6 }
7 for i := 1; i < m; i++ {
8 for j := 1; j < n; j++ {
9 //注意，这里dp[j-1]已经是新一行的数据了，而dp[j]仍然是上一行的数据
10 dp[j] += dp[j - 1]
11 }
12 }
13 return dp[n-1]
14}
（可以看到直接击败99%的用户）
如果上面的题目不太好理解，建议看一下我之前的几道动态规划讲解。基本都是先使用普通DP思路，然后再尝试压缩状态。可能会有一些帮助！
所以，今天的问题你学会了吗？评论区留下你的想法！
小浩算法，每日一题
关注领取《图解算法》高清版
进群的小伙伴请加右侧私人微信（备注：进群）