ayushrocker92's blog

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

How can i solve this problem

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

»
10 years ago, # |
  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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please illustrate it with an example.Consider the given test case example of problem

    → Reply