讨论/题目交流/🐱 第 12 场夜喵双周赛/
🐱 第 12 场夜喵双周赛

欢迎在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 数组变换
4 分 - 力扣排行榜
5 分 - 树的直径
7 分 - 删除回文子数组

展开讨论

第四题的简单解释

要计算数组的最少删除次数,等价于计算数组变成回文数组的最少删除次数+1。
求数组的回文所需次数很简单,首先对于最后一个数,他要么被删除,要么不被删除。
如果被删除,原问题就是规模为n-1的子问题的结果+1。
如果不被删除,,他肯定和前面某个数相同,为了方便描述记为k,那么k前面的数都不能保留都要被删除,那么删除k之前的数组所需要的次数显然是一个规模更小的子问题,同时k之后的数组要计算变成回文数组的最少次数也是个规模更小的子问题。
那么状态转移方程就很自然的知道了。

1
展开全部 12 讨论