Блог пользователя acash

Find minimum cost path in a matrix using dp?
Автор acash, история, 5 лет назад, По-английски

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?

Теги dp
  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

is cost value always non negative?

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

If you can move in all four directions, you have a graph with cycles and then you can't use dp.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If the cost values are non negative is it still true that we can't use dp.

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Yes. Because what would dp transitions look like? There can be no cycles among them.

      → Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    That's how I implemented it can it be more efficient. https://ideone.com/tvKC9r

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can anyone tell me what will be the time complexity of my solution ? I am using dijkstra on a matrix (in above soln) ?

      → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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?

        → Ответить