ayushrocker92's blog

dp+graph
By ayushrocker92, 11 years ago, In English

How can i solve this problem

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

To solve this problem we should use dynamic programming; States will be [last vertex][mask for vertexes];

At every moment we will pick vertex which connected to our last vertex;

And if last vertex is already connected with starting vertex and if we already have at least 3 vertexes in our mask, we should add 1 to answer of this state;

Answer of current state will be d[next vertex][mask + next vertex]

Answer will be d[starting vertex][mask + starting vertex]

Here is my code for better understanding

→ Reply