Description

TL;DR 消消乐

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

Constraints

  • 1≤boxes.length≤100
  • 1≤boxes[i]≤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