多维动态规划 与 树型动态规划

if (A[i - 1] == B[j - 1])
    f[i][j] = f[i - 1][j - 1];                    // 匹配，免费
else
    f[i][j] = min({f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]}) + 1;
//         删除(上)        插入(左)          替换(左上)

void dfs(int u, int fa) {
    // ① 初始化：先把「只考虑 u 自己」的情形写好
    f[u][0] = 0;
    f[u][1] = val[u];

    // ② 递归所有儿子（后序：儿子先算完）
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs(v, u);

        // ③ 把儿子的答案合并到 u 上（这才是每个题的精华所在）
        f[u][0] += max(f[v][0], f[v][1]);
        f[u][1] += f[v][0];
    }
    // ④ 回到 u 之后，f[u] 已经是「u 的整棵子树」的答案
}

for (int j = min(cap, siz[u] + siz[v]); j >= 1; j--)   // ① 倒序枚举总容量
    for (int k = 1; k <= min(j - 1, siz[v]); k++)  // ② 分给 v 的额度 k
        f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);     // ③ 用旧值更新新值
siz[u] += siz[v];                                          // ④ 别忘了更新大小

// 第一遍 DFS：任取 1 为根，算出「只考虑子树」的答案
void dfs1(int u, int fa) {
    siz[u] = 1;
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        down[u] += down[v] + siz[v];   // 例：子树内的距离之和
    }
}

// 第二遍 DFS：把根的答案「平移」给儿子
void dfs2(int u, int fa) {
    for (int v : g[u]) {
        if (v == fa) continue;
        // 以 v 为根时：v 的子树(含 v) 里有 siz[v] 个点，距离各减 1
        //              其余 n - siz[v] 个点，距离各加 1
        ans[v] = ans[u] + (n - siz[v]) - siz[v];
        dfs2(v, u);
    }
}

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

const int MAXN = 2005;
int f[MAXN][MAXN];          // f[i][j]: A 前 i 个 → B 前 j 个 的最少操作数

int main() {
    string A, B;
    cin >> A >> B;
    int n = A.size(), m = B.size();

    // ---- 边界：第一列（全删）与第一行（全插） ----
    for (int i = 0; i <= n; i++) f[i][0] = i;
    for (int j = 0; j <= m; j++) f[0][j] = j;

    // ---- 逐行从左到右填表：保证三个来源都已算过 ----
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (A[i - 1] == B[j - 1])
                f[i][j] = f[i - 1][j - 1];              // 匹配：免费
            else
                f[i][j] = min({f[i - 1][j],          // 删除 A 的第 i 个
                               f[i][j - 1],          // 插入 B 的第 j 个
                               f[i - 1][j - 1]}) + 1;  // 替换
        }
    }
    cout << f[n][m] << "\n";
    return 0;
}

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

const int MAXN = 6005;
int n, r[MAXN], f[MAXN][2];   // f[u][0]: u 不来; f[u][1]: u 来
int indeg[MAXN];                 // 入度，用来找根
vector<int> g[MAXN];

void dfs(int u) {
    f[u][0] = 0;                  // 初始化：只考虑 u 自己
    f[u][1] = r[u];

    for (int v : g[u]) {           // 递归所有直接下属
        dfs(v);
        f[u][0] += max(f[v][0], f[v][1]);  // u 不来：v 随意
        f[u][1] += f[v][0];               // u 来：v 必须不来
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> r[i];
    for (int i = 1; i < n; i++) {
        int l, k; cin >> l >> k;      // k 是 l 的上司
        g[k].push_back(l);
        indeg[l]++;
    }
    int root = 1;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) { root = i; break; }  // 入度为 0 即根

    dfs(root);
    cout << max(f[root][0], f[root][1]) << "\n";
    return 0;
}

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

const int MAXN = 305;
int n, m, s[MAXN], siz[MAXN];
int f[MAXN][MAXN];        // f[u][j]: u 子树中选 j 门（含 u）的最大学分
vector<int> g[MAXN];

void dfs(int u) {
    siz[u] = 1;
    f[u][1] = s[u];                     // 必须选 u 自己（虚根 s[0]=0）

    for (int v : g[u]) {
        dfs(v);
        // ① j 倒序：保证 f[u][j-k] 是「还没考虑 v」的旧值
        for (int j = min(m + 1, siz[u] + siz[v]); j >= 1; j--) {
            // ② k 的上下界：至少给 u 留 1 个位置(k <= j-1)
            //            且不能超过 u 已有的容量(k >= j - siz[u])
            for (int k = max(1, j - siz[u]); k <= min(j - 1, siz[v]); k++)
                f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
        }
        siz[u] += siz[v];                 // ③ 合并完别忘了更新子树大小
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int k; cin >> k >> s[i];
        g[k].push_back(i);                // 0 号是虚根，把森林连成一棵树
    }
    dfs(0);
    cout << f[0][m + 1] << "\n";      // 虚根占 1 个名额
    return 0;
}

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

const int MAXM = 5005;
int f[2][MAXM];              // 只保留两行：f[0][·] 与 f[1][·]

int main() {
    string A, B;
    cin >> A >> B;
    int n = A.size(), m = B.size();

    for (int i = 1; i <= n; i++) {
        int cur = i & 1, pre = (i - 1) & 1;
        f[cur][0] = 0;                  // 每行开头都要重置边界
        for (int j = 1; j <= m; j++) {
            if (A[i - 1] == B[j - 1])
                f[cur][j] = f[pre][j - 1] + 1;   // 配对成功
            else
                f[cur][j] = max(f[pre][j], f[cur][j - 1]);// 丢 A 或丢 B
        }
    }
    cout << f[n & 1][m] << "\n";
    return 0;
}

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

const int MAXN = 100005;
int n, dp[MAXN][2];
vector<int> g[MAXN];

void dfs(int u, int fa) {
    dp[u][0] = 0;                       // u 不选：一个都不用
    dp[u][1] = 1;                       // u 选：先把自己算上

    for (int v : g[u]) {
        if (v == fa) continue;
        dfs(v, u);
        dp[u][0] += dp[v][1];                            // u 不选 → 儿子必须全选
        dp[u][1] += min(dp[v][0], dp[v][1]);             // u 选 → 儿子随意取优
    }
}

int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);              // 无向边，双向加
    }
    dfs(1, 0);
    cout << min(dp[1][0], dp[1][1]) << "\n";
    return 0;
}

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

const int MAXN = 200005;
int n, down[MAXN], up[MAXN];
int best1[MAXN], best2[MAXN], id1[MAXN];  // 最长 / 次长 / 最长来自谁
vector<int> g[MAXN];

// ---------- 第一遍：自底向上求 down ----------
void dfs1(int u, int fa) {
    best1[u] = best2[u] = 0;   // 边权非负，初值 0 安全
    id1[u] = 0;
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs1(v, u);
        int len = down[v] + 1;
        if (len > best1[u]) {          // 刷新最大值，旧的最大值降为次大
            best2[u] = best1[u]; best1[u] = len; id1[u] = v;
        } else if (len > best2[u]) {   // 只刷新次大值
            best2[u] = len;
        }
    }
    down[u] = best1[u];
}

// ---------- 第二遍：自顶向下求 up ----------
void dfs2(int u, int fa) {
    for (int v : g[u]) {
        if (v == fa) continue;
        // 若最长向下链恰好经过 v，则不能再用它，改用次大值
        int fromU = (id1[u] == v) ? best2[u] : best1[u];
        up[v] = max(up[u], fromU) + 1;
        dfs2(v, u);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); g[v].push_back(u);
    }
    up[1] = 0;                      // 根没有「上方」，初始为 0
    dfs1(1, 0);
    dfs2(1, 0);
    for (int i = 1; i <= n; i++)
        cout << max(down[i], up[i]) << " \n"[i == n];
    return 0;
}

int n, siz[MAXN], f[MAXN][MAXV], g[MAXN][2];
vector<int> g2[MAXN];

// ============ 形态一：选与不选（最大权独立集） ============
void dp1(int u, int fa) {
    g[u][0] = 0; g[u][1] = val[u];
    for (int v : g2[u]) {
        if (v == fa) continue;
        dp1(v, u);
        g[u][0] += max(g[v][0], g[v][1]);   // 禁止型约束：儿子自由
        g[u][1] += g[v][0];
    }
}

// ============ 形态二：覆盖型（最小顶点覆盖） ============
void dp2(int u, int fa) {
    g[u][0] = 0; g[u][1] = 1;
    for (int v : g2[u]) {
        if (v == fa) continue;
        dp2(v, u);
        g[u][0] += g[v][1];                     // 要求型约束：儿子必须扛
        g[u][1] += min(g[v][0], g[v][1]);
    }
}

// ============ 形态三：树上背包 ============
void dp3(int u, int fa, int cap) {
    siz[u] = 1; f[u][1] = val[u];          // 必选 u
    for (int v : g2[u]) {
        if (v == fa) continue;
        dp3(v, u, cap);
        for (int j = min(cap, siz[u] + siz[v]); j >= 1; j--)   // 倒序！
            for (int k = max(1, j - siz[u]); k <= min(j - 1, siz[v]); k++)
                f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
        siz[u] += siz[v];
    }
}

// ============ 形态四：换根（两遍 DFS） ============
void reroot1(int u, int fa) {  /* 自底向上：算 down[u] / best1 / best2 / id1 */ }
void reroot2(int u, int fa) {  /* 自顶向下：up[v] = max(up[u], 不过 v 的最长) + 1 */ }