Complexity Analysis Time Complexity: O(N*M), we call our recursive function for every element in the grid.
Space Complexity: O(N*M) , space used to store the 2D DP array.

Space Optimization

Algorithm

If we closely look the relation,

dp[i][j] = matrix[i][j] + max(dp[i-1][j],dp[i-1][j-1], dp[i-1][j+1]))

We see that we only need the previous row, in order to calculate dp[i][j]. Therefore we can space optimize it. Initially, we can take a dummy row (say prev). We initialize this row to the input matrix's first row (as done in tabulation). Now the current row (say cur) only needs the prev row’s value inorder to calculate dp[i][j]. Once we calculate current row's value, we can update previous row for next rows.

Code