本文主要是介绍LeeCode 546 区间 DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意
传送门 LeeCode 546 移除盒子
题解
难以顺序处理，故考虑不断拓展区间。令 d p l , r dp_{l, r} dpl,r 为 [ l , r ) [l,r) [l,r) 的答案，当 b l b_{l} bl 与 b r − 1 b_{r-1} br−1 不在同一轮被移除，则可以枚举分界点更新答案；反之，则难以直接递推。令 f l , r , k f_{l,r,k} fl,r,k 为 [ l , r ) [l, r) [l,r) 中与 b l b_{l} bl 在同一轮被移除的元素数量即可。总时间复杂度 O ( n 4 ) O(n^4) O(n4)。
#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];}
};
这篇关于LeeCode 546 区间 DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
