Unique Paths
找到不重复的能到达目标的路径数
my solution (8ms)
典型的可以用递归解决的问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public:
int uniquePaths(int m, int n) {
_m = m;
_n = n;
_cx = 0;
uniquePaths_do(1, 1);
return _cx;
}
private:
void uniquePaths_do(int m, int n) {
if (m == _m && n == _n) {
++_cx;
return;
}
if (m + 1 <= _m)
uniquePaths_do(m + 1, n);
if (n + 1 <= _n)
uniquePaths_do(m, n + 1);
}
int _m;
int _n;
int _cx;
};
|
结果超时了, 想了一下:
11
21 12
31 22 22 13
41 32 32 23 32 23 23 14
这样子的话, 大多数的迭代都会重复
所以更改了一下代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public:
int uniquePaths(int m, int n) {
_m = m;
_n = n;
return uniquePaths_do(1, 1);
}
private:
int uniquePaths_do(int m, int n) {
auto p = make_pair(m, n);
if (road[p] != 0) {
return road[p];
} else if (m == _m && n == _n) {
return 1;
}
int l = 0, r = 0;
if (m + 1 <= _m)
l = uniquePaths_do(m + 1, n);
if (n + 1 <= _n)
r = uniquePaths_do(m, n + 1);
if (road[p] == 0) {
road[p] = l + r;
}
return l + r;
}
int _m;
int _n;
map <pair<int, int>, int> road;
};
|
通过保存的形式来去掉一些可以重用的计算, 虽然过了, 但是效果不理想
emm… 我没有再从树中能总结出什么好的规律…
the best solution
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> path(m, vector<int>(n, 1));
for(int i = m - 2; i >= 0; i--){
for(int j = n - 2; j >= 0; j--){
path[i][j] = path[i + 1][j] + path[i][j + 1];
}
}
return path[0][0];
}
};
|
简洁又高效, 真是个漂亮的小东西
思路是这样的:
1 1 1
3 2 1
1 1 1
3 2 1
6 3 1
上述分别是 3, 2 和 3, 3 的情况, 假设 rebot 在左下角, star 在右上角(本质上不会有什么改变, 只是换了方向)
从 star 开始往后退, 每一个节点的次数都是他的 上节点次数 + 右节点次数 直到循环结束
最后的左下角就是 rebot 的次数
这样的算法复杂度是 O(n)