P62 不同路径
这道题刚看可能以为是dfs或者bfs来寻找路径。
额 ，我看第一眼感觉应该是dp ， 求每个 【i】【j】位置的不同路径个数
这样， 虽然直接通过了
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> f(m+1,vector<int>(n+1));
f[1][0] = 1;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
f[i][j] = f[i-1][j] + f[i][j-1];
}
}
return f[m][n];
}
};
但是有点慢。
终于 ，其实和刚才差不多
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> f(m+1,vector<int>(n+1 ,1));
for(int i=2;i<=m;i++){
for(int j=2;j<=n;j++){
f[i][j] = f[i-1][j] + f[i][j-1];
}
}
return f[m][n];
}
};
因为第一行和第一列都是1， 所以我们直接遍历别的位置就可以。
好的，就是这样，再见！
