README
¶
题目大意
给定一个数组 [1, 3, 2, 2, 2, 3, 4, 3, 1] 相邻且值相同的数字可以一起删除，如果删除的个数是K，本次删除的总得分就是k*k。把所有数删除完能得到的最高分。
例子：
[1, 3, 2, 2, 2, 3, 4, 3, 1]
----> [1, 3, 3, 4, 3, 1] (3*3=9 points)
----> [1, 3, 3, 3, 1] (1*1=1 points)
----> [1, 1] (3*3=9 points)
----> [] (2*2=4 points)
总得分 23
题解
这是一道n^3的动态规划，而且我的方法做得很复杂，调了很久才调出来。事实上leetcode上有网友的代码非常简单…这里也明白一个道理，虽然都能解出一道题，但是合理和巧妙的状态方程可以把子问题划分得更简单，尽量多的状态让方程去遍历而不是人去枚举，除非像我这样想到一个笨的方程。
所以先说说我的解法：
设f(i,j,k)表示删除boxes[i..j]的所有数字，且最后一次删除刚好删了k个boxes[j]（也就是得k*k分）。所以我们最终的问题就是求Max{f(0,n-1, k)}，其中k∈[1..t]，t表示从0到n-1一共有多少个和boxes[n-1]值相等的数。即使有t个和boxes[j]相等的数，但是删除不一定就要一次删t个，所以这个k需要枚举。
这里我们再定义一个辅助操作 t(i,j)，表示把boxes[i..j]删除能得到的最高分。这里需要注意，t(i,j)实际上就是Max{Max{f(i,j,[k])}}。
基于上面的定义，让我们一起想一想怎么转移。
设M(i,j)表示boxes[i..j]中和boxes[j]相等的数的个数，当我们删除boxes[i..j]时：
- 如果只删boxes[j]一个，那么结果就是t(i,j-1)+1
- 枚举本次要删除的数的个数k，在i..j中找到一个和boxes[j]相同的数boexes[m]，
t(i,j) = f(i,m,k-1) - (k-1)^2+k^2 + t(m+1,j-1)，由于-(k-1)^2+k^2可以化简为2*k-1，所以t(i,j) = Max{f(i,m,k-1) + 2*k-1 + t(m+1,j-1)}，这里m和k都需要枚举。
对于m的枚举，可以一开始预处理一个pre数组，pre[i]表示第i个数前面一个和它相等的数的下标，这就像个链表，所以对于m的枚举就可以变成:
for j >= 0 && pre[j] != -1 {
//...
j = pre[j]
}
对于k的枚举，因为有了pre，所以可以通过pre计算出i..j之间有多少个boxes[j]，也就是上面说的M(i,j)，那么k的枚举范围就是1..M(i,j)。
这里还有个贪心策略可以优化搜索空间，但是调试代码调得我心烦意乱，就没加。但是可以说一说这个策略：
对于数组 [...........x,x,.........]，如果两个相等的数相邻，那么在进行删除操作时，这两数一起删一定比分开删更优。一个简单的证明：
假设把两个数分开删，同时假设第一个x和它前面的m个x一起删最优，第二个x和它后面的n个x一起删最优，那么这两次操作得到的结果是(m+1)^+(n+1)^2。然而，如果把两个x都和前面m个x一起删，得到的结果是(m+2)^2+n^2；如果把两个x和后面n个x一起删得到的结果是m^2+(n+2)^2
我们来比较下这三个值，先把它们展开：
- (m+1)^+(n+1)^2 = m^2+n^2+2m+2n+2
- (m+2)^2+n^2 = m^2+n^2+4m+4
- m^2+(n+2)^2 = m^2+n^2+4n+4
减去公共的(m^2+n^2+2)再同除以2得到：
- 分开删： m+n ...①
- 和前m个一起删： 2m+1 ...②
- 和后n个一起删： 2n+1 ...③
分情况讨论：
- 当m=n时:
- ① = 2m
- ② = 2m+1
- ③ = 2m+1 得到 ①<②=③
- 当m>n时：
- ① = m+n
- ② = 2m+1
- ③ = 2n+1 得到 ①<②
- 当m < n时：
- ① = m+n
- ② = 2m+1
- ③ = 2n+1 得到 ①<③ 综上可得，不论m和n的取值如何，分开删一定不是最优的选择。
结论:
如果两个相邻元素值相同，那么他们一定是一并删除
有了以上结论，假设从boxes[j]开始(包括)往前有q个连续的元素值和它相等，我们在转移时可以: f(i,j,k) = f(i,j-q,k-q) - (k-q)^+k^2
Documentation
¶
There is no documentation for this package.
Source Files