How to get the right DP solution?

Revision en1, by EugeneJudo, 2021-08-16 03:34:08

I worked through https://cses.fi/problemset/task/2413/, but i'm not too happy with my implementation: https://cses.fi/paste/a16f2727089e9e76291e5a/

It's very complicated, as I went with a route I saw would work, but knew would be hard to implement. Every integer represents one of the 20 possible row states, and dp figures out in the next row how many of type X appear based on the sum of the states that allow for type X to appear next. Looking at others solutions, no such enumeration is necessary, but I can't really understand why the alternative method works. Could someone explain the proper approach here?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English EugeneJudo 2021-08-16 03:34:08 649 Initial revision (published)