在leetcode面经上发现一道有意思的题目，大家可以一起讨论一下

rikoizz 发表于 2019-6-16 08:43
cf 3500 的大佬都没做出来....我觉得作为面试题八成是缺少某种约束条件

感觉这个题不像candy crush，更像祖玛啊哈哈。蛤蟆来决定哪段先消除。面试官少给一个参数frog。txtx

这题真的挺有意思的哈哈

感觉和488有点像，期待大神O(n)的解法！

magicsets 发表于 2019-6-16 02:56
这种情况之前确实没有考虑.. 要解决的话可以再加一个状态函数：

给定输入数组S，定义 H(i, j) 取值如 ...

之前描述状态转移方程的时候有点混乱..（但是关于 C(i, j) 和 H(i, j) 的定义应该还是比较明确的）

写了一份代码这样比较好参照：

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <vector>
   
4. 
   
5. constexpr static int kNotSet = -1;
   
6. constexpr static int kInvalid = -2;
   
7. class MaxRepetition;
   
8. 
   
9. // Crushable(i, j) = true 当且仅当 data[i..j] 经过任意变换后可以被完全消除
   
10. class Crushable {
    
11. public:
    
12.   explicit Crushable(const size_t length)
    
13.       : states_(length, std::vector<int>(length, kNotSet)) {}
    
14. 
    
15.   bool Get(int i, int j) {
    
16.     if (states_[i][j] == kNotSet) {
    
17.       states_[i][j] = Evaluate(i, j);
    
18.     }
    
19.     return static_cast<bool>(states_[i][j]);
    
20.   }
    
21. 
    
22.   void SetMaxRepetition(MaxRepetition* max_repetition) {
    
23.     max_repetition_ = max_repetition;
    
24.   }
    
25. 
    
26. private:
    
27.   bool Evaluate(int i, int j);
    
28. 
    
29.   MaxRepetition* max_repetition_;
    
30.   std::vector<std::vector<int>> states_;
    
31. };
    
32. 
    
33. // (1) 如果 data[i] != data[j]，那么 MaxRepetition(i, j) = kInvliad
    
34. // (2) 否则不妨设 data[i] == data[j] == X，那么 MaxRepetition(i, j)
    
35. //     取值为 data[i..j] 经过任意消除过程后可以得到的最长的"全X" 串的长度；
    
36. //     如果不能消除到只剩下X，那么 MaxRepetition(i, j) 取值仍然为kInvalid
    
37. class MaxRepetition {
    
38. public:
    
39.   MaxRepetition(const std::vector<int>& data)
    
40.       : data_(data),
    
41.         states_(data.size(), std::vector<int>(data.size(), kNotSet)) {}
    
42. 
    
43.   int Get(int i, int j) {
    
44.     if (states_[i][j] == kNotSet) {
    
45.       states_[i][j] = Evaluate(i, j);
    
46.     }
    
47.     return states_[i][j];
    
48.   }
    
49. 
    
50.   void SetCrushable(Crushable* crushable) {
    
51.     crushable_ = crushable;
    
52.   }
    
53. 
    
54. private:
    
55.   int Evaluate(int i, int j);
    
56. 
    
57.   const std::vector<int> &data_;
    
58.   Crushable* crushable_;
    
59.   std::vector<std::vector<int>> states_;
    
60. };
    
61. 
    
62. ////////////////////////////////////////////////////////////////////////////////
    
63. /////////////////// Crushable 与 MaxRepetition 的状态转移方程 /////////////////////
    
64. ////////////////////////////////////////////////////////////////////////////////
    
65. 
    
66. bool Crushable::Evaluate(int i, int j) {
    
67.   // 边界条件：区间长度小于3
    
68.   if (i + 1 >= j) {
    
69.     return false;
    
70.   }
    
71.   // 如果存在i < k < j，使得Crushable(i, k)且Crushable(k + 1, j)，那么返回true
    
72.   for (int k = i + 2; k < j - 2; ++k) {
    
73.     if (Get(i, k) && Get(k + 1, j)) {
    
74.       return true;
    
75.     }
    
76.   }
    
77.   // 否则考虑是否可以Crush中间若干区间，然后剩下来的同一字符数量大于等于3
    
78.   return max_repetition_->Get(i, j) >= 3;
    
79. }
    
80. 
    
81. int MaxRepetition::Evaluate(int i, int j) {
    
82.   // 边界条件
    
83.   if (data_[i] != data_[j]) {
    
84.     return kInvalid;
    
85.   }
    
86.   // 区间大小为1或者2的情况
    
87.   if (i + 1 >= j) {
    
88.     return j - i + 1;
    
89.   }
    
90.   int max_count = kInvalid;
    
91.   // Case 1
    
92.   if (crushable_->Get(i + 1, j - 1)) {
    
93.     max_count = 2;
    
94.   }
    
95.   // Case 2
    
96.   const int target_value = data_[i];
    
97.   for (int k = i + 1; k < j; ++k) {
    
98.     if (data_[k] != target_value) {
    
99.       continue;
    
100.     }
     
101.     const int left_count = Get(i, k);
     
102.     const int right_count = Get(k, j);
     
103.     if (left_count != kInvalid && right_count != kInvalid) {
     
104.       max_count = std::max(max_count, left_count + right_count - 1);
     
105.     }
     
106.   }
     
107.   return max_count;
     
108. }
     
109. 
     
110. std::vector<int> ComputeShortestRemnant(const std::vector<int>& data) {
     
111.   const int length = data.size();
     
112.   if (length == 0) {
     
113.     return {};
     
114.   }
     
115. 
     
116.   Crushable crushable(length);
     
117.   MaxRepetition max_repetition(data);
     
118.   crushable.SetMaxRepetition(&max_repetition);
     
119.   max_repetition.SetCrushable(&crushable);
     
120. 
     
121.   // 外层的动态规划：找到总长度最大的Crushable区间集合
     
122.   std::vector<int> max_crush(length);
     
123.   std::vector<int> backtrack(length);
     
124.   backtrack[0] = -1;
     
125.   for (int j = 2; j < length; ++j) {
     
126.     max_crush[j] = max_crush[j - 1];
     
127.     backtrack[j] = j - 1;
     
128.     for (int i = 0; i < j - 1; ++i) {
     
129.       if (crushable.Get(i, j)) {
     
130.         const int total_crush = (i == 0 ? 0 : max_crush[i - 1]) + j - i + 1;
     
131.         if (total_crush > max_crush[j]) {
     
132.           max_crush[j] = total_crush;
     
133.           backtrack[j] = i - 1;
     
134.         }
     
135.       }
     
136.     }
     
137.   }
     
138. 
     
139.   // Backtrack收集无法消除的元素
     
140.   std::vector<int> result;
     
141.   int curr = length - 1;
     
142.   while (curr != -1) {
     
143.     const int prev = backtrack[curr];
     
144.     if (prev == curr - 1) {
     
145.       result.push_back(data[curr]);
     
146.     }
     
147.     curr = prev;
     
148.   }
     
149. 
     
150.   std::reverse(result.begin(), result.end());
     
151.   return result;
     
152. }
     
153. 
     
154. void PrintVector(const std::vector<int>& values) {
     
155.   std::cout << "[";
     
156.   bool first = true;
     
157.   for (int value : values) {
     
158.     std::cout << (first ? "" : " ") << value;
     
159.     first = false;
     
160.   }
     
161.   std::cout << "]\n";
     
162. }
     
163. 
     
164. int main(int argc, char* argv[]) {
     
165.   // [1 1]
     
166.   PrintVector(ComputeShortestRemnant({1,3,3,3,2,2,2,3,1}));
     
167. 
     
168.   // [1 1]
     
169.   PrintVector(ComputeShortestRemnant({1,3,3,3,2,2,2,3,1}));
     
170. 
     
171.   // [3 1 3 2 3]
     
172.   PrintVector(ComputeShortestRemnant(
     
173.       {3,1,2,2,2,1,1,1,2,2,3,1,1,2,2,2,1,1,1,2,3}));
     
174. 
     
175.   // [2]
     
176.   PrintVector(ComputeShortestRemnant({2,3,3,3,2,2,2,3,3}));
     
177. 
     
178.   // []
     
179.   PrintVector(ComputeShortestRemnant({5,1,1,1,5,1,1,1,5}));
     
180. 
     
181.   // []
     
182.   PrintVector(ComputeShortestRemnant({1,1,1,2,2,2,1,2,2,2,1}));
     
183. 
     
184.   // []
     
185.   PrintVector(ComputeShortestRemnant(
     
186.       {3,1,1,1,2,1,1,1,2,1,1,1,2,1,1,1,2,2,1,1,
     
187.        1,3,1,1,1,3,2,2,2,3,1,1,1,3,1,1,1,3}));
     
188. 
     
189.   return 0;
     
190. }
     

复制代码

补充内容 (2019-6-16 14:47):
Crushable对应原帖描述的C(i, j)，MaxRepetition对应原帖描述的H(i, j)，都是用了memo的方法，总时间复杂度为O(n ^ 3）

magicsets 发表于 2019-6-15 12:40
这个问题可以用两阶段的动态规划做吧，时间是O(n^3)，不知道可不可以进一步优化了

--

1. C(i, j)的计算可以参考POJ 1390的题解，用dfs + dp 求解。对于这道题，rlen的长度可以限制在0到3之间。时间复杂度O(n^3)
2. 不需要排序，C(i, j) 是个0/1矩阵，这个矩阵本身决定了区间的顺序。后面对区间做dp时，需要对右端点排序，但是在计算dp[j] 的时候，只需要枚举所有的 C(i, j) 即可。
3. 这题看起来似乎无论如何都无法避免计算C(i, j)。想要有更好的方法，不妨直接考虑如何求解所有的C(i, j)。因为剩下的部分可以在O(n^2)时间内解决