本文共 1472 字,大约阅读时间需要 4 分钟。
初识动态规划。
格点(i,j)。由于只能从上格点(i-1,j)或左格点(i,j-1)到达,并且两者路径是不重复的
因此path[i][j] = path[i-1][j]+path[i][j-1]。
最近要开始看动态规划了。
class Solution {public: int uniquePaths(int m, int n) { vector> ans(m,vector (n,1)); for(int i=1;i
63II 自己写的方法1特复杂。
class Solution {public: int uniquePathsWithObstacles(vector>& obstacleGrid) { //obstacleGrid={ {0,0,0},{0,1,0},{0,0,0}}; int m=obstacleGrid.size(); int n=obstacleGrid[0].size(); int i,j,j1,i1; vector > ans(m,vector (n,1)); if(m>=1&&n>=1) { for(j=0;j
方法2:
class Solution {public: int uniquePathsWithObstacles(vector>& obstacleGrid) { if (obstacleGrid.empty() || obstacleGrid[0].empty() || obstacleGrid[0][0] == 1) return 0; vector > dp(obstacleGrid.size(), vector (obstacleGrid[0].size(), 0)); for (int i = 0; i < obstacleGrid.size(); ++i) { for (int j = 0; j < obstacleGrid[i].size(); ++j) { if (obstacleGrid[i][j] == 1) dp[i][j] = 0; else if (i == 0 && j == 0) dp[i][j] = 1; else if (i == 0 && j > 0) dp[i][j] = dp[i][j - 1]; else if (i > 0 && j == 0) dp[i][j] = dp[i - 1][j]; else dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } return dp.back().back(); }};
转载地址:http://nnwmj.baihongyu.com/