题目
连接
思路
思路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]。