数据结构与算法-动态规划-区间dp,状态机dp,树形dp

3-区间 DP

介绍

通常用 (dp[i][j]) 表示区间 ([i, j]) 上的某种最优值，比如 (dp[i][j]) 可以表示从下标 (i) 到 (j) 的元素进行某种操作所得到的最大收益、最小花费等。
状态转移方程：这是区间 DP 的关键。它描述了如何从较小的区间的最优解得到较大区间的最优解。例如，对于一个表达式求值问题，可能有 (dp[i][j] = max{dp[i][k] + dp[k + 1][j] + text{合并操作}(i, k, j)})，其中 (i leq k < j)，即通过枚举区间 ([i, j]) 内的分割点 (k)，将区间 ([i, j]) 拆分成两个子区间 ([i, k]) 和 ([k + 1, j])，然后根据具体问题的要求进行合并操作。

初始化：一般需要初始化长度为 1 的区间，即 (dp[i][i]) 的值，这通常根据问题的具体情况来确定。例如在某些问题中， (dp[i][i]) 可能表示单个元素的某种属性值。

计算顺序：按照区间长度从小到大的顺序进行计算。先计算长度为 2 的区间的 (dp) 值，再计算长度为 3 的区间，以此类推，直到计算出长度为 (n)（问题规模）的区间的 (dp) 值。这样可以保证在计算较大区间时，其所依赖的小区间的最优解已经计算出来。
 

模板

cpp

// 初始化for (int i = 1; i <= n; i++) {

    dp[i][i] = 初始值; }

// 区间长度从 2 开始递增for (int len = 2; len <= n; len++) {

    for (int i = 1; i + len - 1 <= n; i++) {

        int j = i + len - 1;

        for (int k = i; k < j; k++) {

            dp[i][j] = 某种状态转移; 

        }

    }}

例题：石子合并问题

在一个圆形操场的四周摆放 N 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 2 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。试计算出将 N 堆石子合并成 1 堆的最小得分和最大得分。

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

const int N = 210;  // 因为要处理环形，数组长度翻倍

const int INF = 0x3f3f3f3f;

int f[N][N], g[N][N];  // f 记录最大得分，g 记录最小得分

int pre[N];  // 前缀和数组

int n;

int a[N];

int main() {

    cin >> n;

    for (int i = 1; i <= n; i++) {

        cin >> a[i];

        a[i + n] = a[i];  // 复制数组以处理环形

    }

    // 计算前缀和

    for (int i = 1; i <= 2 * n; i++) {

        pre[i] = pre[i - 1] + a[i];

    }

    // 初始化 f 和 g 数组

    memset(f, -INF, sizeof f);

    memset(g, INF, sizeof g);

    for (int i = 1; i <= 2 * n; i++) {

        f[i][i] = g[i][i] = 0;

    }

    // 动态规划计算

    for (int len = 2; len <= n; len++) {

        for (int i = 1; i + len - 1 <= 2 * n; i++) {

            int j = i + len - 1;

            for (int k = i; k < j; k++) {

                f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + pre[j] - pre[i - 1]);

                g[i][j] = min(g[i][j], g[i][k] + g[k + 1][j] + pre[j] - pre[i - 1]);

            }

        }

    }

    // 找出长度为 n 的区间的最小和最大得分

    int max_score = -INF, min_score = INF;

    for (int i = 1; i <= n; i++) {

        max_score = max(max_score, f[i][i + n - 1]);

        min_score = min(min_score, g[i][i + n - 1]);

    }

    cout << min_score << endl << max_score;

    return 0;

}    

4-状态机 DP

介绍

状态机 DP 引入了状态机的概念，帮助我们更好地进行状态转移。通过定义不同的状态，明确状态之间的转移关系，从而找出合适的状态转移方程。常见的有 2 状态、3 状态甚至 k 状态的情况。

模板

cpp

// 初始化状态数组memset(dp, 初始值, sizeof dp);

// 遍历每个阶段for (int i = 1; i <= n; i++) {

    // 遍历每个状态

    for (int j = 0; j < 状态数; j++) {

        // 根据状态转移方程更新状态

        dp[i][j] = 某种状态转移; 

    }}

例题 1：大盗阿福

不能抢相邻的店铺，设置两个状态：0 表示不抢，1 表示抢。

代码

cpp

#include <iostream>#include <algorithm>#include <cstring>using namespace std;

const int N = 100010;int f[N][2];int a[N];int n;

int main() {

    int T;

    cin >> T;

    while (T--) {

        cin >> n;

        for (int i = 1; i <= n; i++) cin >> a[i];

        f[0][0] = 0, f[0][1] = -0x3f3f3f3f;

        for (int i = 1; i <= n; i++) {

            f[i][1] = f[i - 1][0] + a[i];

            f[i][0] = max(f[i - 1][0], f[i - 1][1]);

        }

        cout << max(f[n][0], f[n][1]) << endl;

    }

    return 0;}

例题 2：股票交易问题

给定一个整数数组 prices 和一个整数 k，其中 prices[i] 是某支给定的股票在第 i 天的价格。最多可以完成 k 笔交易，不能同时参与多笔交易（必须在再次购买前出售掉之前的股票），计算所能获取的最大利润。

代码

#include <iostream>

#include <vector>

#include <cstring>

#include <algorithm>

using namespace std;

class Solution {

public:

    int maxProfit(int k, vector<int>& prices) {

        int n = prices.size();

        int f[1010][101][2];

        memset(f, -0x3f, sizeof f);

        for (int i = 0; i <= n; i++) f[i][0][0] = 0;

        for (int i = 1; i <= n; i++) {

            for (int j = 1; j <= min(i, k); j++) {

                f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + prices[i - 1]);

                f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i - 1]);

            }

        }

        int ans = 0;

        for (int i = 1; i <= k; i++) ans = max(ans, f[n][i][0]);

        return ans;

    }

};    

同理可以加入股票冷冻期变成3个状态：可购入，可卖出，冷冻期
当然还有k状态的，很多很多，总之状态机是为了让我们可以更好的找出转移方程

5-树形 DP

介绍

算法如其名，在树形结构上的dp问题，经常搭配dfs一起食用
定义：树形 DP 以树作为数据结构，利用树的递归性质和无环特性，自底向上或自顶向下地在树上进行状态转移，从而求解问题的最优解。与一般动态规划类似，树形 DP 通过把原问题分解为多个子问题，并保存子问题的解来避免重复计算，以提高算法效率。

原理基础：树的每个节点及其子树构成一个独立的子问题，父节点的状态往往依赖于子节点的状态。例如，在一棵表示家族关系的树中，要计算整个家族的某种属性（如财富总值），可以先计算每个子家族（以每个子节点为根的子树）的该属性值，再汇总到根节点。

定义状态：根据问题的性质，为树的每个节点定义合适的状态。状态通常包含与该节点及其子树相关的信息，例如，在计算树中最长路径问题时，可能定义状态为从该节点出发到子树中某一叶子节点的最长路径长度。

确定状态转移方程：这是树形 DP 的关键步骤。根据问题的逻辑，确定父节点状态如何由子节点状态推导得出。例如，对于求树的最大独立集（选取一些节点，使得任意两个选取的节点不相邻，且选取节点数量最多）问题，对于某节点i，其状态转移方程可能为：选择节点i时，最大独立集大小等于该节点值加上所有孙子节点的最大独立集大小之和；不选择节点i时，最大独立集大小等于所有子节点的最大独立集大小之和。即dp[i][0] = max(dp[i][0], dp[j][1])（j为i的子节点，表示不选i），dp[i][1] = w[i] + sum(dp[k][0])（k为j的子节点，表示选i，w[i]为节点i的值）。

选择遍历顺序：

自底向上：从叶子节点开始，逐步向上更新节点状态，直到根节点。这种方式适用于子节点状态确定后，父节点状态可以直接推导的问题。例如在计算树的节点深度时，叶子节点深度为 0，通过叶子节点深度可以计算其父节点深度，以此类推直到根节点。

自顶向下：从根节点出发，递归地向子节点传递信息并更新状态。适用于父节点状态影响子节点状态计算的问题。比如在一些需要考虑从根到当前节点路径信息的问题中，根节点的信息可以在向下遍历过程中传递给子节点。

初始化状态：根据问题的具体情况，为树的节点初始化状态值。例如，对于一些计数问题，可能初始值设为 0；对于求最值问题，可能初始值设为负无穷（求最大值时）或正无穷（求最小值时）。

计算结果：经过状态转移后，根节点的状态值通常就是问题的解。例如在计算树的直径（树中最长路径的长度）问题中，根节点最终计算得到的状态值就是树的直径。
 

模板

cpp

// 定义树的邻接表

vector<int> tree[N];// 定义状态数组int dp[N][状态数];

// 深度优先搜索函数void dfs(int u, int fa) {

    // 初始化当前节点的状态

    dp[u][状态] = 初始值; 

    // 遍历当前节点的子节点

    for (int i = 0; i < tree[u].size(); i++) {

        int v = tree[u][i];

        if (v == fa) continue;

        dfs(v, u);

        // 根据状态转移方程更新当前节点的状态

        dp[u][状态] = 某种状态转移; 

    }}

例题：大学职员宴会问题

某大学有 n 个职员，他们之间有从属关系，形成一棵以校长为根的树。宴会每邀请来一个职员都会增加一定的快乐指数，但如果某个职员的直接上司来参加舞会了，那么这个职员就不肯来参加舞会。计算邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

#include <bits/stdc++.h>

using namespace std;

const int N = 6010;

int a[N];

int n;

unordered_map<int, vector<int>> p;

int is[N] = {0};

int ans = 0;

int f[N][2] = {0};

void dfs(int e) {

    f[e][1] = a[e];

    for (int i = 0; i < p[e].size(); i++) {

        int son = p[e][i];

        dfs(son);

        f[e][1] += f[son][0];

        f[e][0] += max(f[son][0], f[son][1]);

    }

}

int main() {

    cin >> n;

    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    for (int i = 0; i < n - 1; i++) {

        int u, v;

        cin >> u >> v;

        is[u] = 1;

        p[v].push_back(u);

    }

    int boss = 0;

    for (int i = 1; i <= n; i++) {

        if (!is[i]) {

            boss = i;

            break;

        }

    }

    dfs(boss);

    cout << max(f[boss][1], f[boss][0]);

    return 0;

}    

例题：树的直径问题

树的直径是树中最长路径的长度。可以使用 f1 和 f2 两个数组，通过一次 DFS 计算出树的直径。

代码

cpp

#include <iostream>#include <vector>#include <cstring>using namespace std;

const int N = 10010;

vector<pair<int, int>> tree[N];int f1[N], f2[N];int ans = 0;

void dfs(int u, int fa) {

    f1[u] = f2[u] = 0;

    for (int i = 0; i < tree[u].size(); i++) {

        int v = tree[u][i].first;

        int w = tree[u][i].second;

        if (v == fa) continue;

        dfs(v, u);

        int t = f1[v] + w;

        if (t > f1[u]) {

            f2[u] = f1[u];

            f1[u] = t;

        } else if (t > f2[u]) {

            f2[u] = t;

        }

    }

    ans = max(ans, f1[u] + f2[u]);}

int main() {

    int n;

    cin >> n;

    for (int i = 0; i < n - 1; i++) {

        int u, v, w;

        cin >> u >> v >> w;

        tree[u].push_back({v, w});

        tree[v].push_back({u, w});

    }

    dfs(1, -1);

    cout << ans << endl;

    return 0;}

例题：树的中心问题

树的中心是指树中一个节点，使得该节点到树中其他节点的最大距离最小。可以使用 up、f1、f2 三个数组，通过两次 DFS 解决。第一次 DFS 求出 f1、f2 并记录 f1 的转移路径，第二次 DFS 计算出 up。

代码

cpp

#include <iostream>#include <vector>#include <cstring>#include <algorithm>using namespace std;

const int N = 10010;

vector<pair<int, int>> tree[N];int f1[N], f2[N], up[N], p1[N];int ans = 0x3f3f3f3f;

void dfs1(int u, int fa) {

    f1[u] = f2[u] = 0;

    for (int i = 0; i < tree[u].size(); i++) {

        int v = tree[u][i].first;

        int w = tree[u][i].second;

        if (v == fa) continue;

        dfs1(v, u);

        int t = f1[v] + w;

        if (t > f1[u]) {

            f2[u] = f1[u];

            f1[u] = t;

            p1[u] = v;

        } else if (t > f2[u]) {

            f2[u] = t;

        }

    }}

void dfs2(int u, int fa) {

    for (int i = 0; i < tree[u].size(); i++) {

        int v = tree[u][i].first;

        int w = tree[u][i].second;

        if (v == fa) continue;

        if (p1[u] == v) {

            up[v] = max(up[u], f2[u]) + w;

        } else {

            up[v] = max(up[u], f1[u]) + w;

        }

        dfs2(v, u);

    }}

int main() {

    int n;

    cin >> n;

    for (int i = 0; i < n - 1; i++) {

        int u, v, w;

        cin >> u >> v >> w;

        tree[u].push_back({v, w});

        tree[v].push_back({u, w});

    }

    dfs1(1, -1);

    dfs2(1, -1);

    for (int i = 1; i <= n; i++) {

        ans = min(ans, max(up[i], f1[i]));

    }

    cout << ans << endl;

    return 0;}