I am learning DP and I am a litle frustrated. I am stucked in this problem http://codeforces.net/problemset/problem/466/C I drew some pictures to find out some states this is the image http://i61.tinypic.com/de4rpe.jpg theres is a pattern in these pictures to get this formula n = n — 2 numberOfTotalCombinations = n * (n-1) / 2 the worst case(5 * 10^5) would be = 124999750000 and it will not pass. My questions Should I consider all the combinations? How to define my states? How I need to construct a DP solution based on the previous states? Thansk in advance and sorry for my bad english