This was strikingly similar to a recent TopCoder problem: http://www.topcoder.com/stat?c=problem_statement&pm=11193&rd=14241 http://www.topcoder.com/stat?c=prob

This was strikingly similar to a recent TopCoder problem: http://www.topcoder.com/stat?c=problem_statement&pm=11193&rd=14241 http://www.topcoder.com/stat?c=problem_statement&pm=1119... I've run into a few problems like this. The simplest solution exploits the property that there is an ordering on the states, so each "later" state can depend only on "earlier" states or itself. A more general EV problem would require Gaussian elimination instead of DP. Fun stuff, all in all.