DP概要

可能用到的题单：

• 能力提升综合题单Part4 动态规划1 - 题单 - 洛谷 | 计算机科学教育新生态
• 【动态规划】普及~省选的dp题 - 题单 - 洛谷 | 计算机科学教育新生态
• 能力提升综合题单Part4 动态规划2 - 题单 - 洛谷 | 计算机科学教育新生态

线性DP

背包DP

区间DP

状压DP

树形 DP

详细参照： 树形类专题

P1040 加分二叉树

前序遍历：

auto print = [&](auto self, int l, int r) {
	if (r < l)return;
	if (l == r) {
		cout << l << " ";return;
	}
	cout << root[l][r] << " ";
	self(self, l, root[l][r] - 1);
	self(self, root[l][r] + 1, r);
	};
print(print, 1, n);

记忆化搜索

#define int long long
int f[40][40], root[40][40];
void solve() {
    int n;cin >> n;vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i], f[i][i] = a[i];
    auto dfs = [&](auto self, int l, int r)->int {
        if (f[l][r] > 0)return f[l][r];
        if (l == r)return a[l];
        if (r < l)return 1;
        for (int i = l;i <= r;i++) {
            int p = self(self, l, i - 1) * self(self, i + 1, r) + a[i];
            if (p > f[l][r]) {
                f[l][r] = p;root[l][r] = i;
            }
        }
        return f[l][r];
        };
    cout << dfs(dfs, 1, n) << '\n';
}

区间 DP

#define int long long
int f[40][40], root[40][40];
void solve() {
    int n;cin >> n;vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i], f[i][i] = a[i], f[i][i - 1] = 1;
    for (int i = n;i >= 1;i--) {
        for (int j = i + 1;j <= n;j++) {
            for (int k = i;k <= j;k++) {
                if (f[i][j] < f[i][k - 1] * f[k + 1][j] + a[k]) {
                    f[i][j] = f[i][k - 1] * f[k + 1][j] + a[k];
                    root[i][j] = k;
                }
            }
        }
    }
    cout << f[1][n] << '\n';
}