Reader, you already know how we start such questions. We break the question in 3 parts: Storage & Meaning, Direction and Travel & Solve.

STORAGE & MEANING

It's fairly simple. We make an array for DP of the dimensions same as that of the maze i.e. n*m.

The meaning assigned to a single cell in this grid is that "to travel from that cell to the destination cell, what is the minimum cost to traverse out of all the paths".

DIRECTION

We always try to solve the question for a simpler and smaller problem via which we move on to the bigger problem.

**We want you to meditate on the fact that to travel from the bottom right cell i.e. dp[n-1][m-1] to the the destination cell dp[n-1][m-1], the minimum cost of the path is the same as the cost of the cell corresponding to the input array (according to the "Meaning" we assigned for a single cell).**

Why do you think it is so?

It's because we can't take a step in horizontal or vertical direction when we are already at the cell dp[n-1][m-1] and the maze comes to an end after that.

Hence our smaller problem lies at the bottom right or dp[n-1][m-1] cell. So we move from right to left direction in columns for every row from bottom to top while calculating the minimum cost.

Figure 3 is the DP array (drawn in green to differentiate from the input array) which denotes the direction of solving the dp array from bottom to top row.

TRAVERSE & SOLVE

In figure 4, we notice that the total cost to travel from source to destination via A,B and C is 200, 320 and 170. Hence, we take the route with the least cost i.e. path via C.

Reader, we apply the similar logic to our maze.

To find the minimum cost from B, we have only one choice to go horizontally right because we can't go vertically down as the maze comes to an end there.

Hence the minimum cost stored at B in the DP array is the sum of the original input array value at the cell B and the previous cell to its right i.e. 8+2=10.

**BASE CASES :**

Similarly, C, D, E, F and G have the only option to move a step horizontally as the maze comes to an end beyond that. Hence minimum cost at each cell is the sum of the original input value at that cell and cost at its previous cell to the right . Hence the DP array would look something like this:

Let's go through this traversal one more time.

We calculate the cost for the cell above '2' and it has only one option, to go in the vertical downwards direction. Hence its minimum cost is 9+2=11.

For cell X, we have 2 options, it can go horizontally right i.e. to 11 or vertically down i.e. to 10. Since 10< 11, therefore X chooses the vertical path and stores 0+10=10 in it.

Try to find the minimum costs for all the cells with this method and tally your result with ours.

Hence we find that to move from the source top left cell to the destination bottom right cell, the minimum cost is 36.

Have a look at the following code.