题目：62. 不同路径

思路

动态规划

代码

以下展示3种方法：

动态规划

// f[i][j] : 到达[i][j]的路径数

// f[i][j] = f[i-1][j] + f[i][j-1];

// f[0][0] = 1,

// i: 0->m, j:0->n

//

class Solution {

public:

int uniquePaths(int m, int n) {

int i, j;

vector> f(m, vector(n, 0));

// 初始化

for(i = 0; i < m; i++)

{

f[i][0] = 1;

}

for(j = 0; j < n; j++)

{

f[0][j] = 1;

}

for(i = 1; i < m; i++)

{

for(j = 1; j < n; j++)

{

f[i][j] = f[i-1][j] + f[i][j-1];

}

}

return f[m-1][n-1];

}

};

深度搜索

用递归暴力遍历呗；

class Solution {

private:

int dfs(int i, int j, int m, int n) {

if (i > m || j > n) return 0; // 越界了

if (i == m && j == n) return 1; // 找到一种方法，相当于找到了叶子节点

return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);

}

public:

int uniquePaths(int m, int n) {

return dfs(1, 1, m, n);

}

};

数论

从起点到终点，向下位移m-1步，向右位移n-1步，所以不管怎么走，其中一定有m-1步向下，n-1向右，不同的方法向下向右的顺序不同而已； 所以到终点的路径数量为一个组合数：m+n-2中取m-1； 写代码时注意数据溢出；

class Solution {

public:

int uniquePaths(int m, int n) {

long long numerator = 1; // 分子

int denominator = m - 1; // 分母

int count = m - 1;

int t = m + n - 2;

while (count--) {

numerator *= (t--);

while (denominator != 0 && numerator % denominator == 0) {

numerator /= denominator;

denominator--;

}

}

return numerator;

}

};

精彩内容

评论可见，请评论后查看内容，谢谢！！！评论后请刷新页面。