Description

TL;DR 消消乐

给出一个数组\(boxes[0, n)\)，数组每个元素均为正整数。每一次操作可以从中消掉一些相同数值的元素，直至数组为空。每消除\(k\)个元素得到的贡献是\(k^2\)，求最大贡献

Constraints

  • \(1 \le boxes.length \le 100\)
  • \(1 \le boxes[i] \le 100\)

Solution

关键在于定义\(dp\)的含义：设\(dp[l][r][x]\)为区间\([l,r]\)且\(r\)右侧拥有与\(boxes[r]\)相同数值的\(x\)个元素

定义好就可以递推了

Code

class Solution {
public:
    int removeBoxes(vector<int>& boxes) {
        int dp[101][101][101];
        memset(dp, 0, sizeof dp);
        auto dfs = [&](auto &&dfs, int l, int r, int x) {
            if(l == r) return (x+1) * (x+1);
            if(l > r) return 0;
            if(dp[l][r][x]) return dp[l][r][x];
            // [l, r-1], [r, x...)
            int ans = dfs(dfs, l, r-1, 0) + dfs(dfs, r, r, x);
            for(int i = l; i < r; ++i) {
                // [l, i], [i+1, r-1], [r, x...)
                if(boxes[i] == boxes[r]) {
                    ans = max(ans, dfs(dfs, i+1, r-1, 0) + dfs(dfs, l, i, x+1));
                } else {
                    ans = max(ans, dfs(dfs, l, i, 0) + dfs(dfs, i+1, r-1, 0) + dfs(dfs, r, r, x));
                }
            }
            return dp[l][r][x] = ans;
        };

        return dfs(dfs, 0, boxes.size()-1, 0);
    }
};

LeetCode-546 Remove Boxes