Recently, I've came across a DP problem. Problem 455A After a while I can't seem to think of any solution so i read the tutorial. Then i've totally lost. I can't understand how the solution work. Anyone can help me ?

P/s : And if you can explain me why could people come up with that solution ( I mean their thoughts process ), that would be a huge help. Anyway, help me pls. I'm stuck !!!

// If anything, forgive me for my bad english. I'm not a native speaker.