C++ ✅ || 10 Lines Code🔥 || Beats 100 % ✅ || Easy Approach ✅✅
"Dynamic programming is the art of solving problems by breaking them into simpler overlapping subproblems, optimizing solutions for efficiency. 🔄"Intuition 🤔The
# "Dynamic programming is the art of solving problems by breaking them into simpler overlapping subproblems, optimizing solutions for efficiency. 🔄"
![Screenshot 2024-12-20 211056.png](https://assets.leetcode.com/users/images/e6144130-e0eb-400e-a782-9313103752ca_1734930850.8095152.png)


# Intuition 🤔
The problem is to find the number of unique paths from the top-left to the bottom-right corner of a grid with obstacles. At each step, movement is allowed either right ➡️ or down ⬇️, and the goal is to count paths while avoiding cells with obstacles. The key observation is to use dynamic programming to store the number of paths to each cell, ensuring to account for obstacles.

# Approach 🛠️
- Create a DP table where each entry represents the number of paths to reach that cell.
- Initialize the starting cell (0,0) with 1, as it's the starting point.
- For the first row and column, paths are only possible if there are no obstacles in the way. 
- For the rest of the grid, if a cell is not blocked, the number of paths to that cell is the sum of the paths from the cell above and the cell to the left. If there’s an obstacle, the number of paths is 0.

# Complexity 📊
- Time complexity: $$O(m \cdot n)$$
- Space complexity: $$O(m \cdot n)$$

# Code 💻
```cpp
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>>memo(m,vector<int>(n,0));
        if (obstacleGrid[0][0] == 1) return 0;
        memo[0][0] = 1;
        for (int i = 1; i < m; i++) if(obstacleGrid[i][0] != 1) memo[i][0] = memo[i-1][0];
        for (int j = 1; j < n; j++) if(obstacleGrid[0][j] != 1) memo[0][j] = memo[0][j-1];
        for(int i=1;i<m;i++) for(int j=1;j<n;j++){
            if(obstacleGrid[i][j] == 1) memo[i][j] = 0;
            else memo[i][j] = memo[i-1][j] +  memo[i][j-1];
        } 
        return memo[m-1][n-1]; 
    }
};
```
![upvote.jpeg](https://assets.leetcode.com/users/images/8fa3df1a-4bff-4fae-b960-836a0fa9f676_1734930830.753764.jpeg)

['Array', 'Dynamic Programming', 'Matrix', 'C++']