Min Cost find

Question

Given a $M\times N$ matrix where each cell has cost associated with it, we need to find the min cost to reach last cell (M-1,N-1) of the matrix from first cell (0,0). We can only move one unit right or one unit down from any cell.

Given below matrix, what will be min cost from (0,0) to (4,4)

$\begin{bmatrix} 4 &7 &8 &6 &4 \\ 6& 7 &3 &9 &2 \\ 3& 8 & 1 & 2 &4 \\ 7&1 &7 &3 &7 \\ 2 &9 &8 &9 &3 \end{bmatrix}$

Comments

ohh, will take too much time

---

i know random is not the right way but try solving with grouping numbers with small weights and try to access that path it works most of the time. if some groups exist like in your question 3 - 1 - 2 - 3 in the middle .

---

type of real life greedy approach :p but sadly greedy does not provide optimal path every time :(