gXa's blog

Dynamic Programming
By gXa, history, 8 years ago, In English

Hi, please provide an algorithm for this question: Click

I am trying it from long time but couldn't reach a proper algo.

  • Vote: I like it
  • -17
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The number of possible paths is 2*(n*(n-1)+2), so you can solve it by brute force

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Can you explain how you got this number?

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Okay I got it, just confirming:

    For each vertex in one row there are N-1 vertices that end the Hamiltonian path.

    Plus for vertex 1 and N there are N ways so that 2.

    As there are 2 rows so finally multiplied by 2.

    → Reply