we have to find min cost path in a mtrix from top left to bottom right.
Move allowed -> Right,left,Bottom,Up.
I know suitable approach will be using Dijkstra But can we do this using Dp because here we can move in all 4 direction ,If yes then How?
we have to find min cost path in a mtrix from top left to bottom right.
Move allowed -> Right,left,Bottom,Up.
I know suitable approach will be using Dijkstra But can we do this using Dp because here we can move in all 4 direction ,If yes then How?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
is cost value always non negative?
If you can move in all four directions, you have a graph with cycles and then you can't use dp.
If the cost values are non negative is it still true that we can't use dp.
Yes. Because what would dp transitions look like? There can be no cycles among them.
That's how I implemented it can it be more efficient. https://ideone.com/tvKC9r
Can anyone tell me what will be the time complexity of my solution ? I am using dijkstra on a matrix (in above soln) ?
Ffs, make a loop over adjacent cells. Don't repeat the same piece of code 4 times.
What is the number of states (vertices of a graph)? What is the number of transitions (edges)? And finally, what is the complexity of Dijkstra?