I was trying to solve this problem from ICL2015div2 finals. I understand this is a problem on combinatorics (and perhaps DP) but I could not find a way towards solution.

I am weak in DP problems. They seem overwhelming to me most of the times. An elaborate explanations will surely be helpful for me. :)

Thanks in advance.

You're right, it is a DP problem. So here's my solution:

Well that was nice. :)

Let me know how do you approach a dp problem? I mean I really find it tough to make an approach to such problems.

Thanks again.

Here's a good tutorial for DP: https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/