Time Complexity: O(N*M), we call our recursive function for every element in the grid.
Space Complexity: O(N*M) + O(N), space used to store memo table and recursive stack space.

Tabulation

Algorithm

To avoid using extra auxiliary stack space, we can convert our memoized solution into tabulation solution. The steps to convert to the tabular solution are given below:

Declare a dp array of size N*M. Initialize the base condition values, i.e the first row of the dp array to the first row of the input matrix.
We want to move from the first row to the last row. Whenever we compute values for a cell, we want to have all the values required to calculate it.
If we see the memoized code, values required for dp[i][j] are: dp[i-1][j], dp[i-1][j-1] and dp[i-1][j+1]. So we only need the values from the previous row.
We have already filled the first row, if we start from row 1 and move downwards we will find the values correctly.
At last we need to return the minimum among the last row of dp array as our answer.

Code

1