62. 不同路径 - 力扣(LeetCode)
思路:
-
使用动态规划
-
-
确定dp数组以及下标的含义
dp[i][j]
的定义为:dp[i][j]
代表到达[i,j]
的路径数量
-
确定递推公式
- 状态转移方程为
dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
- 状态转移方程为
-
dp数组如何初始化
// 要初始化左边第一排和上边第一排的所有格子路径数为1 for(int i = 0; i < n; ++i) { dp[0][i] = 1; } for(int i = 0; i < m; ++i) { dp[i][0] = 1; } -
确定遍历顺序
// 因为左边第一排和上面第一排已经初始化 for(int i = 1; i < m; ++i) { for(int j = 1; j < n; ++j) { } }
-
我的AC代码
动态规划
// 时间复杂度O(n x m),空间复杂度O(n x m) class Solution { public: int uniquePaths(int m, int n) { vector<vector<int>> dp(m, vector<int>(n, 0)); for(int i = 0; i < n; ++i) { dp[0][i] = 1; } for(int i = 0; i < m; ++i) { dp[i][0] = 1; } for(int i = 1; i < m; ++i) { for(int j = 1; j < n; ++j) { dp[i][j] += dp[i - 1][j] + dp[i][j - 1]; } } return dp[m - 1][n -1]; } };
标准答案
动态规划
// 时间复杂度O(n x m),空间复杂度O(n x m) class Solution { public: int uniquePaths(int m, int n) { vector<vector<int>> dp(m, vector<int>(n, 0)); for (int i = 0; i < m; i++) dp[i][0] = 1; for (int j = 0; j < n; j++) dp[0][j] = 1; for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } return dp[m - 1][n - 1]; } };
动态规划(优化空间复杂度)
// 时间复杂度O(n x m),空间复杂度O(n) class Solution { public: int uniquePaths(int m, int n) { vector<int> dp(n); for (int i = 0; i < n; i++) dp[i] = 1; for (int j = 1; j < m; j++) { for (int i = 1; i < n; i++) { dp[i] += dp[i - 1]; } } return dp[n - 1]; } };
数论方法
// 时间复杂度O(m),空间复杂度O(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; } };
63. 不同路径 II - 力扣(LeetCode)
思路:
-
使用动态规划
-
-
确定dp数组以及下标的含义
dp[i][j]
的定义为:dp[i][j]
代表到达[i,j]
的路径数量
-
确定递推公式
// 遇到障碍物则赋为0 if(obstacleGrid[i][j] == 1) { dp[i][j] = 0; } else { dp[i][j] += dp[i -1][j] + dp[i][j - 1]; } -
dp数组如何初始化
// 要初始化左边第一排和上边第一排的所有格子路径数为1 // 遇到障碍物就直接中断 for(int i = 0; i < m; ++i) { if(obstacleGrid[i][0] == 1) { break; } dp[i][0] = 1; } for(int i = 0; i < n; ++i) { if(obstacleGrid[0][i] == 1) { break; } dp[0][i] = 1; } -
确定遍历顺序
// 因为左边第一排和上面第一排已经初始化 for(int i = 1; i < m; ++i) { for(int j = 1; j < n; ++j) { } }
-
我的AC代码
动态规划
// 时间复杂度O(m x n),空间复杂度O(m x n) class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); vector<vector<int>> dp(m, vector<int>(n, 0)); for(int i = 0; i < m; ++i) { if(obstacleGrid[i][0] == 1) { break; } dp[i][0] = 1; } for(int i = 0; i < n; ++i) { if(obstacleGrid[0][i] == 1) { break; } dp[0][i] = 1; } for(int i = 1; i < m; ++i) { for(int j = 1; j < n; ++j) { if(obstacleGrid[i][j] == 1) { dp[i][j] = 0; } else { dp[i][j] += dp[i -1][j] + dp[i][j - 1]; } } } return dp[m - 1][n -1]; } };
标准答案
动态规划
// 时间复杂度O(m x n),空间复杂度O(m x n) class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) //如果在起点或终点出现了障碍,直接返回0 return 0; vector<vector<int>> dp(m, vector<int>(n, 0)); for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1; for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1; for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (obstacleGrid[i][j] == 1) continue; dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } return dp[m - 1][n - 1]; } };
动态规划(空间优化版)
// 时间复杂度:O(n × m),n、m 分别为obstacleGrid 长度和宽度 // 空间复杂度:O(m) class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { if (obstacleGrid[0][0] == 1) return 0; vector<int> dp(obstacleGrid[0].size()); for (int j = 0; j < dp.size(); ++j) if (obstacleGrid[0][j] == 1) dp[j] = 0; else if (j == 0) dp[j] = 1; else dp[j] = dp[j-1]; for (int i = 1; i < obstacleGrid.size(); ++i) for (int j = 0; j < dp.size(); ++j){ if (obstacleGrid[i][j] == 1) dp[j] = 0; else if (j != 0) dp[j] = dp[j] + dp[j-1]; } return dp.back(); } };
Comments NOTHING