LeeCode 546 区间 DP

题意

传送门 LeeCode 546 移除盒子

题解

难以顺序处理，故考虑不断拓展区间。令 $d{p}_{l,r}$ 为 $[l,r)$ 的答案，当 $b_l$ 与 $b_{r-1}$ 不在同一轮被移除，则可以枚举分界点更新答案；反之，则难以直接递推。令 $f_{l,r,k}$ 为 $[l,r)$ 中与 $b_l$ 在同一轮被移除的元素数量即可。总时间复杂度 $O(n^4)$。

#include <bits/stdc++.h>
using namespace std;

constexpr int N = 100;
class Solution {
   
   public:
    int f[N][N + 1][N + 1], dp[N][N + 1];
    int removeBoxes(vector<int>& boxes) {
   
        int n = boxes.size();
        const int inf = 1e9;
        for (int i = 0; i < n; ++i) {
   
            for (int j = 0; j <= n; ++j) {
   
                dp[i][j] = -inf;
                for (int k = 0; k <= n; ++k) {
   
                    f[i][j][k] = -inf;
                }
            }
        }
        for (int i = 0; i < n; ++i) {
   
            f[i][i + 1][1] = 0;
            dp[i][i + 1] = 1;
        }
        auto get_max = [&](int& x, int y) {
   
            x = max(x, y);
        };
        for (int w = 2; w <= n; ++w) {
   
            for (int l = 0; l + w <= n; ++l) {
   
                int r = l + w;
                for (int k = 1; k <= r - l; ++k) {
   
                    if (boxes[l] == boxes[r - 1]) {
   
                        get_max(f[l][r][k], f[l][r - 1][k - 1]);
                    }
                    for (int m = l + 1; m < r; ++m) {
   
                        get_max(f[l][r][k], f[l][m][k] + dp[m][r]);
                    }
                    get_max(dp[l][r], f[l][r][k] + k * k);
                }
            }
        }
        return dp[0][n];
    }
};