Day 39 动态规划
62. 不同路径
递归(深搜)
使用递归的方法超时(可以过37个case)
class Solution {
int goPath(int m, int n, int curRow, int curCol)
{
if (curRow == m - 1 && curCol == n - 1)
{
return 1;
}
if (curRow >= m || curCol >= n)
{
return 0;
}
return goPath(m, n, curRow + 1, curCol) + goPath(m, n, curRow, curCol + 1);
}
public:
int uniquePaths(int m, int n) {
return goPath(m, n, 0, 0);
}
};
来分析一下时间复杂度,这个深搜的算法,其实就是要遍历整个二叉树。
这棵树的深度其实就是m+n-1(深度按从1开始计算)。
那二叉树的节点个数就是 2^(m + n - 1) - 1。可以理解深搜的算法就是遍历了整个满二叉树(其实没有遍历整个满二叉树,只是近似而已)文章来源:https://www.toymoban.com/news/detail-660018.html
所以上面深搜代码的时间复杂度为O(2^(m + n - 1) - 1),可以看出,这是指数级别的时间复杂度,是非常大的。文章来源地址https://www.toymoban.com/news/detail-660018.html
迭代
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> table(m, vector<int>(n, 0));
for (int i = 0; i < m; i++) table[i][0] = 1;
for (int i = 0; i < n; i++) table[0][i] = 1;
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
{
table[i][j] = table[i - 1][j] + table[i][j - 1];
}
}
return table[m - 1][n - 1];
}
};
63. 不同路径II
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
vector<vector<int>> table(obstacleGrid.size(), vector<int>(obstacleGrid[0].size(), 0));
for (int i = 0; i < table.size(); i++)
{
if (obstacleGrid[i][0]) break;
table[i][0] = 1;
}
for (int i = 0; i < table[0].size(); i++)
{
if (obstacleGrid[0][i]) break;
table[0][i] = 1;
}
for (int i = 1; i < table.size(); i++)
{
for (int j = 1; j < table[0].size(); j++)
{
if (obstacleGrid[i][j]) continue;
table[i][j] = table[i - 1][j] + table[i][j - 1];
}
}
return table[table.size() - 1][table[0].size() - 1];
}
};
到了这里,关于算法刷题Day 39 不同路径+不同路径II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!