# 0546. Remove Boxes
###### tags: `Leetcode` `DFS+Memorization` `Medium`
Link: https://leetcode.com/problems/remove-boxes/
## 思路
一开始的想法是每次把相同的array merge起来
然后正常做backtracking 发现会TLE
其实看了正确思路的讲解之后发现用这种思路不一定会得到正确答案 因为有可能连续的数字被拆开会更好
### 正确思路
参考[这里](https://leetcode.com/problems/remove-boxes/discuss/1402561/C%2B%2BJavaPython-Top-down-DP-Clear-explanation-with-Picture-Clean-and-Concise)

## Code

class Solution {
    int[][][] dp;
    public int removeBoxes(int[] boxes) {
        int n = boxes.length;
        dp = new int[n][n][n];
        return dfs(boxes, 0, n-1, 0);
    }
    private int dfs(int[] boxes, int l, int r, int k){
        if(l>r) return 0;
        if(dp[l][r][k]>0){
            return dp[l][r][k];
        }
        int lOrg = l, kOrg = k;
        while(l+1<=r && boxes[l]==boxes[l+1]){
            l++; 
            k++;
        }
        int ans = (k+1)*(k+1)+dfs(boxes, l+1, r, 0);
        for(int i=l+1; i<=r; i++){
            if(boxes[i]==boxes[l]){
                ans = Math.max(ans, dfs(boxes, l+1, i-1, 0)+dfs(boxes, i, r, k+1));
            }
        }
        return dp[lOrg][r][kOrg] = ans;
    }
}

### TLE思路

class Solution {
    public int removeBoxes(int[] boxes) {
        List<int[]> interval = new ArrayList<>();
        for(int i=0; i<boxes.length; i++){
            if(i==0 || boxes[i-1]!=boxes[i]){
                interval.add(new int[]{boxes[i], 1});
            }
            else{
                int num = interval.get(interval.size()-1)[1];
                interval.remove(interval.size()-1);
                interval.add(new int[]{boxes[i], num+1});
            }
        }
        Map<String, Integer> dp = new HashMap<>();
        return dfs(interval, dp);
    }
    private int dfs(List<int[]> interval, Map<String, Integer> dp){
        List<int[]> newInterval = new ArrayList<>();
        for(int i=0; i<interval.size(); i++){
            if(newInterval.size()==0 || newInterval.get(newInterval.size()-1)[0]!=interval.get(i)[0]) newInterval.add(interval.get(i));
            else{
                int num = newInterval.get(newInterval.size()-1)[1];
                newInterval.remove(newInterval.size()-1);
                newInterval.add(new int[]{interval.get(i)[0], num+interval.get(i)[1]});
            }
        }
        if(dp.containsKey(newInterval.toString())) return dp.get(newInterval.toString());
        int max = 0;
        for(int i=0; i<newInterval.size(); i++){
            List<int[]> next = new ArrayList<>(newInterval);
            next.remove(i);
            max = Math.max(max, newInterval.get(i)[1]*newInterval.get(i)[1]+dfs(next, dp));
        }
        dp.put(newInterval.toString(), max);
        return max;
    }
}