C++刷LeetCode（546. 移除盒子）【动态规划*】【递归*】

糖逗

题目描述：

1. 
   
2. 给出一些不同颜色的盒子，盒子的颜色由数字表示，即不同的数字表示不同的颜色。
   
3. 你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k*k 个积分。
   
4. 当你将所有盒子都去掉之后，求你能获得的最大积分和。
   
5. 
   
6. 
   
7. 
   
8. 示例：
   
9. 
   
10. 输入：boxes = [1,3,2,2,2,3,4,3,1]
    
11. 输出：23
    
12. 解释：
    
13. [1, 3, 2, 2, 2, 3, 4, 3, 1]
    
14. ----> [1, 3, 3, 4, 3, 1] (3*3=9 分)
    
15. ----> [1, 3, 3, 3, 1] (1*1=1 分)
    
16. ----> [1, 1] (3*3=9 分)
    
17. ----> [] (2*2=4 分)
    
18. 
    
19. 
    
20. 提示：
    
21. 
    
22. 1 <= boxes.length <= 100
    
23. 1 <= boxes[i] <= 100

复制代码

1. class Solution {
   
2. public:
   
3.     int dp[100][100][100];
   
4.     int currsion(vector<int>& boxes, int l, int r, int k) {
   
5.         if (l > r) return 0;
   
6.         if (dp[l][r][k] != 0) return dp[l][r][k];
   
7.         dp[l][r][k] = calculatePoints(boxes, l, r - 1, 0) + (k + 1) * (k + 1);
   
8.         for (int i = l; i < r; i++) {
   
9.             if (boxes[i] == boxes[r]) {
   
10.                 dp[l][r][k] = max(dp[l][r][k], currsion(boxes, l, i, k + 1) + currsion(boxes, i + 1, r - 1, 0));
    
11.             }
    
12.         }
    
13.         return dp[l][r][k];
    
14.     }
    
15. 
    
16.     int removeBoxes(vector<int>& boxes) {
    
17.         memset(dp, 0, sizeof dp);
    
18.         return calculatePoints(boxes, 0, boxes.size() - 1, 0);
    
19.     }
    
20. };

复制代码

参考链接：https://leetcode-cn.com/problems ... -leetcode-solution/    下的评论区