动态规划

    1. class Solution {
    2. public:
    3.     int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    4.         int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    5.         if (obstacleGrid.size() ==0 || obstacleGrid[0][0] == 1) return 0;
    6.         int row = obstacleGrid.size();
    7.         int col = obstacleGrid[0].size();
    8.         vector<vector<int>> dp(row, vector<int>(col, 0));
    9.         for (int i = 0; i < row; i++) {
    10.             for (int j = 0; j < col; j++) {
    11.                 if (obstacleGrid[i][j] == 1) {
    12.                     dp[i][j] = 0;
    13.                     continue;
    14.                 }
    15.                 if (i == 0 && j == 0) dp[i][j] = 1;
    16.                 else if (i == 0) dp[i][j] = dp[i][j-1];    //注意初始化边界的时候，一定不能直接写成1，因为边界上可能存在障碍物！！！
    17.                 else if (j == 0) dp[i][j] = dp[i-1][j];
    18.                 else dp[i][j] = dp[i-1][j] + dp[i][j-1];
    19.             }
    20.         }
    21.         return dp[row-1][col-1];
    22.     }
    23. };
    25. -- 优化：将dp数组多初始化一行一列。这样可以不用初始化dp首行和首列，直接调用dp方程即可； 
    26.     此时要注意obstacleGrid 中的i,j判断是要减1，因为比dp数组少一行一列
    27. class Solution {
    28. public:
    29.     int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    30.         int row = obstacleGrid.size();
    31.         int col = obstacleGrid[0].size();
    32.         vector<vector<int>> dp(row + 1, vector<int>(col + 1, 0));
    33.         dp[0][1] = 1; //dp[1][0] 也可以
    34.         for (int i = 1; i <= row; ++i) {
    35.             for (int j = 1; j <= col; ++j) {
    36.                 if (obstacleGrid[i-1][j-1] == 0)
    37.                     dp[i][j] = dp[i-1][j] + dp[i][j-1];
    38.             }
    39.         }
    40.         return dp[row][col];
    41.     }
    42. };