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

Автор rahul_1234, история, 6 лет назад, По-английски

Given a matrix of n*n. Each cell contain 0, 1, -1.

0 denotes there is no diamond but there is a path. 1 denotes there is diamond at that location with a path -1 denotes that the path is blocked.

Now you have start from 0,0 and reach to last cell & then return back to 0,0 collecting maximum no of diamonds. While going to last cell you can move only right and down. While returning back you can move only left and up.

Теги #dp
  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

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

This also came in one of my tests. Couldn't come up with anything good. One thing is clear that running naive algorithm twice will give incorrect results.

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

    It is same as two paths moving simultaneously from start to end. So we can see the distance travelled is always same i.e there are on same diagonal at each moment. So a dp with states as (diagonal,pos1,pos2) can be done with O(1) transitions. Hence O(n*n*n).