力扣 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}。
d p [ i ] [ j ] dp[i][j] dp[i][j] ：到达点 i i i 和 j j j 的最多路径。
转移式子如下：
d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] dp[i][j] = dp[i - 1][j] + dp[i][j - 1] dp[i][j]=dp[i−1][j]+dp[i][j−1]
d p [ 1 ] [ j ] dp[1][j] dp[1][j] 和 d p [ i ] [ 1 ] dp[i][1] 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 ( m n ) O(mn) O(mn)的。
我们观察， d p [ i ] [ j ] dp[i][j] dp[i][j]是由 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i−1][j] 和 d p [ i ] [ j − 1 ] dp[i][j-1] dp[i][j−1] 转移过来的。
我们画图：
红色是目前准备更新的值，其只与绿色和蓝色的值有关。
我们尝试利用 背包思想 把他们进行压缩：
我们把他们压缩成一维，数组中每个值的含义与我们枚举 j j j 的顺序有关：
我们观察上图，可以发现，需要从左向右枚举 j 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维后， d p [ j ] dp[j] dp[j] 的含义仍然是走到 j j j 列，共多少种走法。
因此 d p dp dp数组初始化为1，因为 d p [ 1 ] = 1 dp[1] = 1 dp[1]=1，走到第 1 1 1 列 就一种走法。
最终输出 d p [ n ] dp[n] dp[n]。
