一直在堅持

來自專欄礦工

關注liss_H加入演算法群。公眾號主要推送與數學演算法科技前沿相關的東西。趕快關注吧！

1. Unique Paths II

A robot is located at the top-left corner of a m x ngrid (marked Start in the diagram below).The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked Finish in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.Example 1:Input:[ [0,0,0], [0,1,0], [0,0,0]]Output: 2Explanation:There is one obstacle in the middle of the 3x3 grid above.There are two ways to reach the bottom-right corner:1. Right -> Right -> Down -> Down2. Down -> Down -> Right -> Right

參考程序(Revise from java)：

static int x = [](){ std::ios::sync_with_stdio(false); cin.tie(NULL); return 0; }();class Solution {public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { if(obstacleGrid.empty()) return 0; int m = obstacleGrid.size(); // rows int n = obstacleGrid[0].size(); // columns if( m==0||n==0||obstacleGrid[0][0] == 1) return 0; vector<int> dp(n); // dp[] represent the current max possible paths dp[0] = 1; for(int k = 1;k<n;++k) //based on previous condition,dp[k-1] not 1 dp[k] = obstacleGrid[0][k] == 1?0:dp[k-1]; for(int i =1;i<m;++i){ dp[0] = obstacleGrid[i][0] ==1?0:dp[0]; //dp[0] not 1 for(int j =0;j<n;++j) dp[j] = obstacleGrid[i][j] == 1?0:dp[j-1] + dp[j]; } return dp[n-1]; }};

推薦閱讀：