openjudge 8471 切割回文

这道题大佬们是怎么想到AC的思路的？

蒟蒻原先试了下线性dp，然后蒟蒻怎么也推不出状态转移方程，一点思路都没有；再试了一下区间dp，写完代码后提交发现n立方的时间复杂度直接tle……看完题解才知道只用n平方就够了~~（不愧是蒟蒻）~~

感觉dp好灵活……刷了二三十道黄题难度的dp发现黄题dp还是很多不会写，很想知道大佬们是怎么得到思路的

~~放点水：~~还有就是，不论是dp还是其他什么题，只要是绿题及以上难度的题蒟蒻不看题解就不会写了，就算看题解也还是很吃力……大佬们是什么时候可以轻松A过绿题的？什么时候可以轻松A过蓝题、紫题（乃至黑题）的？

感谢大佬指教