力扣 T62 不同路径

题目

连接

思路

思路1 ： BFS爆搜

class Solution {
public:queue<pair<int,int>>q;int uniquePaths(int m, int n) {q.push({1,1});  // 起始位置vector<pair<int, int>> actions;actions.push_back({0, 1});  // 向下actions.push_back({1, 0});   // 向右int ans = 0;while(!q.empty()){auto s = q.front();q.pop();for(auto action : actions){int x = s.first, y = s.second;if(x == n && y == m) {ans ++; break;}x += action.first, y += action.second;if(x <= n && y <= m) q.push({x, y});}}return ans;}
};

超时了。

思路2： dp

我们将起始点编号为 { 1 , 1 } \{1,1\} {1,1}。
设finish点为： { 2 , 3 } \{2, 3\} {2,3}。
$dp[i][j]$ ：到达点$i$ 和$j$ 的最多路径。
转移式子如下：
$$dp[i][j]=dp[i-1][j]+dp[i][j-1]$$
$dp[1][j]$ 和$dp[i][1]$ 均为1.

class Solution {
public:int uniquePaths(int m, int n) {int dp[105][105];for(int i = 0; i <= m; i++) for (int j = 0; j <= n;j++) dp[i][j] = 1;for(int i = 2; i <= m; i++){for(int j = 2; j <= n; j++){dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m][n];}
};

复杂度优化

我们可以优化空间复杂度。原本空间复杂度是$O(mn)$的。
我们观察，$dp[i][j]$是由 $dp[i-1][j]$ 和$dp[i][j-1]$ 转移过来的。
我们画图：

红色是目前准备更新的值，其只与绿色和蓝色的值有关。
我们尝试利用 背包思想 把他们进行压缩：
我们把他们压缩成一维，数组中每个值的含义与我们枚举$j$ 的顺序有关：

我们观察上图，可以发现，需要从左向右枚举$j$。

代码

class Solution {
public:int uniquePaths(int m, int n) {int dp[105];for(int i = 0 ; i < 105; i++) dp[i] = 1;for(int i = 2; i <= m; i++){for(int j = 2; j <= n; j++){dp[j] += dp[j - 1];}}return dp[n];}
};

注意
dp数组压缩成1维后，$dp[j]$ 的含义仍然是走到$j$ 列，共多少种走法。
因此$dp$数组初始化为1，因为$dp[1]=1$，走到第$1$ 列 就一种走法。
最终输出$dp[n]$。