Đường đi duy nhất II trong C++

Giả sử có một robot ở góc trên bên trái của lưới n x m (n hàng, m cột). Robot chỉ có thể đi xuống hoặc sang phải. Robot muốn đến góc dưới bên phải (đánh dấu 'END').

Một số ô trong lưới bị chặn (obstacles). Ta phải tìm số lượng đường đi duy nhất có thể. Ví dụ, lưới [[0,0,0],[0,1,0],[0,0,0]] sẽ như sau:

Robo
	Obs
		END

Kết quả là 2, có 2 cách khác nhau từ đầu đến cuối:

Phải → Phải → Xuống → Xuống
Xuống → Xuống → Phải → Phải

Các bước thực hiện:

a := số hàng, b := số cột
nếu grid[a – 1,b - 1] khác 0, return 0
Tạo bảng DP kích thước a x b
for i := b – 1 xuống 0
- nếu grid[a – 1, i] break, ngược lại DP[a – 1, i] := 1
for i := a – 1 xuống 0
- nếu grid[i, b - 1] break, ngược lại DP[i, b – 1] := 1
for i := a – 2 xuống 0
- for j := b – 2 xuống 0
  - DP[i, j] := DP[i + 1, j] + DP[i, j + 1] khi grid[i, j] = 0, ngược lại 0
return DP[0, 0]

Hãy xem triển khai sau để hiểu rõ hơn:

Ví dụ

#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution {    public:    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {       int a = obstacleGrid.size();       int b = obstacleGrid[0].size();          if(!a || !b) return 0;       if(obstacleGrid[a - 1][b - 1])return 0;       vector < vector <lli> > dp(a, vector <lli>(b));       for(int i = b - 1; i >= 0; i--)if(obstacleGrid[a-1][i]) break; else dp[a-1][i] = 1;       for(int i = a - 1; i >= 0; i--)if(obstacleGrid[i][b - 1]) break; else dp[i][b-1] = 1 ;       for(int i = a-2; i >= 0; i--){          for(int j = b-2 ; j >= 0; j--)dp[i][j] = !obstacleGrid[i][j]? dp[i+1][j] + dp[i][j+1] : 0;       }       return dp[0][0];    } }; main(){    Solution ob;    vector<vector<int>> v = {{0,0,0},{0,1,0},{0,0,0}};    cout << ob.uniquePathsWithObstacles(v); }

Input

[[0,0,0],[0,1,0],[0,0,0]]

Đường đi duy nhất II trong C++

Ví dụ

Input

Output