Preamble

Have you ever come across a problem that you couldn't solve, and that even after many people explaining it to you, you still couldn't understand?

Ever since I participated in the Round 923 Div 3 contest, I have kept the problem G — Paint Charges in the back of my mind. I have tried to understand how to solve it reading the editorial quite a few times, also how other people solved it in completely different ways. At a certain point, I couldn't help but feel quite frustrated that there were several ways to solve the problem, but all of them felt alien to me: "How on earth would I figure out that I want to use i,j and k meaning x,y and z, and that they are enough to describe the DP state for this problem? How am I supposed to find out that the transitions between the states are done like this?"

So I just had to come to terms with the fact that dynamic programming was a very weak point of mine, and to decide to put some work on finding the answers to my questions. I started solving some variations of coin change problems, 0-1 knapsack, longest increasing sequence (all of which I had done before, but feeling uncomfortable revisiting them after a while). Every now and then I would think "hey, let me check that Paint Charges again, maybe I have learned something now that could help me design a DP solution for it. No dice. OK, I'll keep solving some more problems and reading what some algorithms/competitive programming books authors have to say about DP",

I eventually came across this thread on CS StackExchange, where the answer was "a good strategy for designing a DP is to formulate the problem recursively and generate sub-problems that way", complemented by Jeff Erickson's comment: "I claim that's the only strategy." Intrigued, I also went on to read Jeff Erickson's Algorithms, where I found this gem: "Many algorithms students ... make the mistake of focusing on the table ... instead of the much more important (and difficult) task of finding a correct recurrence."

That made a lot of sense. I need to find the correct recurrence, otherwise even if I read the editorial and it says that I can solve it using i, j and k representing x, y and z, I still have no idea how I could came up with those parameters meaning what they mean, or how they are related.

I also kept this insight in the back of my mind. However... that was still not enough for me to figure out how to solve the Paint Charges problem.

The road to ACC

Some weeks and some contests ahead, I was still thinking every now and then about how to solve the problem, and after solving quite a few other DP problems, while walking my dog, I kind of had an epiphany: what if I just try to solve it as a regular 0-1 knapsack problem?

Take 1: 0-1-knapsack-like DP solution (TLE)

In one typical 0-1 knapsack problem, we have the knapsack capacity, a set of objects, and for each object, we know how much it weights and how much it costs, and we want to find the maximum value that we can get from objects put in the knapsack. The DP solution goes like: "for an object, say, the last (or the first) one, an optimum solution must be to either put it in the knapsack or not. If I put it, then my remaining capacity decreases, and then I have to find the optimum solution for a decreased capacity and one less object. If I don't put it, then I have to find the optimum solution for the same capacity and one less object."