Complexity Analysis

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix. This is because we are filling up a 2D DP array of size m x n, and each cell takes constant time to compute.

Space Complexity: O((N-1)+(M-1)) + O(M*N) We are using a recursion stack space: O((N-1)+(M-1)), here (N-1)+(M-1) is the path length and an external DP Array of size ‘M*N’.

Tabulation Approach

Algorithm

Declare a dp[] array of size [m][n] where m and n are the dimensions of the matrix. The dp array stores the results of subproblems. Specifically, dp[i][j] represents the total number of ways to reach the destination (0,0) from the cell (i,j).
Set the base case for the array: In the recursive solution, when i = 0 and j = 0, we have one way to reach there. Therefore, set dp[0][0] = 1, indicating that we have reached the destination.
Use two nested loops to iterate through the dp array. For each cell, calculate the number of ways to reach it from the top (up) and from the left (left), as we did in the recursive approach. If mat[i][j] is a blocked cell (i.e., the value is 1), set dp[i][j] = 0 to indicate that no path exists through that cell.
At each cell, if i > 0 and j > 0, compute dp[i][j] = dp[i-1][j] + dp[i][j-1] to account for the number of ways to reach (i,j) from the previous row and column. If the cell is blocked, we ensure that dp[i][j] remains 0.
After filling in the entire dp array, return dp[m-1][n-1] because it will contain the total number of ways to reach the bottom-right corner of the grid, which is the final solution to the problem.