Investigating in how many ways objects of two different colors can be grouped
This is an interesting problem. It is not so easy. What is more difficult is to implement an efficient algorithm.
My algorithm is trying to make each partition "ordered". But my code is not running very fast. It takes 1.8 second to get the answer.
After I checked the discussion. I found a very clever algorithm by daniel.is.fischer and implemented by Robert_Gerbicz. It is extremely fast, only need 4 ms or even less! This is an excellent example of dynamic programming!
No comments:
Post a Comment