LeetCode题练习与总结：移除盒子--546

一、题目描述

给出一些不同颜色的盒子 boxes ，盒子的颜色由不同的正数表示。

你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k * k 个积分。

返回 你能获得的最大积分和 。

示例 1：

输入：boxes = [1,3,2,2,2,3,4,3,1]
输出：23
解释：
[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 分)

示例 2：

输入：boxes = [1,1,1]
输出：9

示例 3：

输入：boxes = [1]
输出：1

提示：

1 <= boxes.length <= 100
1 <= boxes[i] <= 100

二、解题思路

定义状态：我们使用三维数组 dp[l][r][k] 来表示从 boxes[l] 到 boxes[r] 的区间，其中 boxes[r] 后面有 k 个与 boxes[r] 相同颜色的盒子时，可以得到的最大积分。
状态转移：对于每个状态 dp[l][r][k]，我们需要考虑以下几种情况：
- 从 r 开始向左找到第一个与 boxes[r] 颜色不同的盒子 p，那么 dp[l][r][k] 可以通过移除 boxes[p+1] 到 boxes[r] 的盒子来计算，即 dp[l][p][0] + (k+1)*(k+1)。
- 从 r 开始向左找到第一个与 boxes[r] 颜色相同的盒子 p，则我们可以将 boxes[p+1] 到 boxes[r-1] 的区间和 boxes[r] 后面的 k 个相同颜色的盒子合并，即 dp[l][p][k+1] + dp[p+1][r-1][0]。
递归和记忆化：由于状态转移是递归的，我们可以使用递归函数实现，并通过三维数组 dp 来记忆化已经计算过的状态，避免重复计算。

三、具体代码

public class Solution {
    public int removeBoxes(int[] boxes) {
        int[][][] dp = new int[100][100][100];
        return dfs(boxes, dp, 0, boxes.length - 1, 0);
    }

    private int dfs(int[] boxes, int[][][] dp, int l, int r, int k) {
        if (l > r) return 0;
        if (dp[l][r][k] != 0) return dp[l][r][k];
        
        // 移除连续相同的盒子
        while (r > l && boxes[r] == boxes[r - 1]) {
            r--;
            k++;
        }
        
        // 计算初始积分
        dp[l][r][k] = dfs(boxes, dp, l, r - 1, 0) + (k + 1) * (k + 1);
        
        // 尝试合并中间的同色盒子
        for (int i = l; i < r; i++) {
            if (boxes[i] == boxes[r]) {
                dp[l][r][k] = Math.max(dp[l][r][k], dfs(boxes, dp, l, i, k + 1) + dfs(boxes, dp, i + 1, r - 1, 0));
            }
        }
        
        return dp[l][r][k];
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

时间复杂度分析需要考虑递归函数 dfs 被调用的次数以及每次调用时的操作数量。

递归调用次数：
- 对于每个状态 (l, r, k)，我们需要考虑所有可能的分割点 i，其中 l <= i < r。在最坏的情况下，对于每个状态，我们需要尝试所有可能的分割点，这会有 O(r - l) 的复杂度。
- 由于状态 (l, r, k) 是递归定义的，并且 l 和 r 的范围是从 0 到 boxes.length - 1，我们需要对每个可能的 l 和 r 组合进行递归。在最坏的情况下，这会导致 O(n^2) 的递归调用次数，其中 n 是 boxes 数组的长度。
每次调用的操作数量：
- 在每次递归调用中，我们有一个循环来遍历所有可能的分割点 i，这会导致 O(r - l) 的操作。
- 因此，每次递归调用的操作数量是 O(n)。

结合上述两点，总的时间复杂度是递归调用次数乘以每次调用的操作数量，即 O(n^2) * O(n) = O(n^3)。

2. 空间复杂度

空间复杂度主要取决于递归调用栈的深度和用于记忆化存储的三维数组 dp。

递归调用栈：
- 递归调用栈的深度在最坏情况下与递归调用的次数相同，即 O(n^2)。
记忆化数组 dp：
- dp 是一个三维数组，其大小为 100 x 100 x 100，因此其空间复杂度是 O(1)，因为这是一个固定的常数大小，与输入数组 boxes 的长度无关。

综上所述，总的空间复杂度是递归调用栈的深度加上记忆化数组 dp 的大小，即 O(n^2) + O(1) = O(n^2)。

因此，该算法的时间复杂度是 O(n^3)，空间复杂度是 O(n^2)。

五、总结知识点

动态规划（Dynamic Programming）：
- 动态规划是一种用于求解最优化问题的算法思想，它将问题分解为相互重叠的子问题，并通过求解子问题来构建原问题的解。
递归（Recursion）：
- 递归是一种编程技巧，函数直接或间接地调用自身，用于解决可以分解为更小相似问题的问题。
记忆化搜索（Memoization）：
- 记忆化是一种优化技术，用于提高函数的效率，通过存储昂贵的函数调用结果，并在需要时返回缓存的结果，避免重复计算。
多维数组（Multi-dimensional Array）：
- 代码中使用了一个三维数组 dp 来存储中间状态的结果，以实现记忆化。
循环和条件判断：
- 代码中使用了 while 循环来处理连续相同颜色的盒子，以及 for 循环来尝试所有可能的分割点。
- if 语句用于检查是否可以合并中间的同色盒子。
状态转移方程：
- 代码中的核心是状态转移方程，它定义了如何从一个或多个已知状态推导出新的状态。
数学运算：
- 代码中使用了加法、乘法和取最大值（Math.max）等基本数学运算。
数组操作：
- 代码中涉及数组的索引访问和更新操作。
面向对象编程（OOP）：
- 代码封装在一个 Solution 类中，这是面向对象编程的一个基本概念。
递归终止条件：
- 递归函数 dfs 中有一个基础情况，即当 l > r 时返回 0，这是递归终止的条件。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。

标签：盒子,递归,--,复杂度,int,boxes,546,移除,dp
From： https://blog.csdn.net/weixin_62860386/article/details/145126307