题目
给出一些不同颜色的盒子,盒子的颜色由数字表示,即不同的数字表示不同的颜色。
你将经过若干轮操作去去掉盒子,直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子(k >= 1),这样一轮之后你将得到 k*k 个积分。
当你将所有盒子都去掉之后,求你能获得的最大积分和。示例 1:
输入:
1 [1, 3, 2, 2, 2, 3, 4, 3, 1]输出:
1 23解释:
1
2
3
4
5 [1, 3, 2, 2, 2, 3, 4, 3, 1]
----> [1, 3, 3, 4, 3, 1] (3*3=9 分)
----> [1, 3, 3, 3, 1] (1*1=1 分)
----> [1, 1] (3*3=9 分)
----> [] (2*2=4 分)提示:盒子的总数 n 不会超过 100。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/remove-boxes
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解
本题看答案看不懂,最终参考https://blog.csdn.net/STILLxjy/article/details/85106608。
这道题是 hard 的动态规划,难点在于我们根本不知道如何进行动态规划,以及为什么动态规划。
由于题目要求是找最大,所以最坏情况我们需要遍历数组的全排列,找到一个结果最大的全排列,时间复杂度$O(N!)$,方法是回溯法。
然而我们知道,这个类似连连看的设定,使得消除一个数的时候,如果能将相同并相邻的数一并消除,此时结果一定优于单独删除此数。
接下来选取状态,为了表示一个子数组,我们需要两个边界,因此至少是一个二维数组,来存放该子数组对应的最大值。因为我们只能用这个二维数组表示连续子数组,所以在选择删除对象时,只能选择某个边界值,而不能从中间删除。
接下来考虑状态转移方程,假设我们删除左边界元素,那么我们需要一并删除与左边界元素相同且相邻的所有元素,此外,数组内部也可能存在被其他数字隔开的相同数字,先把这些阻挡的数字删掉,再一并删除所有连续且与左边界元素相同的数字,这样可能可以取得更大的结果。
换个角度看,把目光看向左边界元素,动态规划的选择其实就是我要么现在消掉,要么留着跟右侧被隔开的元素合并再消掉,两种取最优。
而为了记录当前左边界元素左侧有多少个连续的相同元素,我们需要增加一个状态,因此变成一个三维动态规划。
以下是递归实现:
1 | class Solution { |
没用 vector 的原因是似乎会爆内存(据说),因此我也就不尝试了,多拿数组练练手没啥不好。
此方法的时间复杂度为$O(N^4)$,需要填满$N^3$大小的数组,每次状态转移需要$O(N)$复杂度,因为递归体中存在循环。