动态规划 Dynamic Programming

背包

01背包

01背包问题通常为：给定 $n$ 种物品和一个背包，第 $i$ 个物品体积为 $c_i$ ，价值为 $w_i$ ，背包地容量为 $C$ 。如何选择装入背包的物品，使装入背包中的物品的总价值最大？

以 HDU 2602 为例

题目

用自底向上的递推完成转移过程， $dp[i][j]$ 表示把前 $i$ 个物品(从第 $1$ 个到第 $i$ 个)装入容量为 $j$ 的背包中获得的最大价值。假设现在递推到 $dp[i][j]$ ，分两种情况：

(1) 第 $i$ 个物品的体积比 $j$ 还大，则不能装入当前背包，直接继承前 $i-1$ 个物品装入容量为 $j$ 的背包，即

$$dp[i][j] = dp[i-1][j]$$

(2) 第i个物品体积比j小，能装进背包，又分为两种：装或不装

• ①装

  $$dp[i][j] = dp[i-1][j-c[i]] + w[i]$$

• ②不装

  $$dp[i][j] = dp[i-1][j]$$

取①②中的最大值，状态转移方程为

$$dp[i][j] = max(dp[i-1][j-c[i]]+w[i],dp[i-1][j])$$

代码

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

const int N = 1001;
int w[N],c[N],dp[N][N];

int solve(int n,int C){
    for(int i=1;i<=n;i++)		//第i个物品 
        for(int j=0;j<=C;j++){	//容量为j 
            if(c[i] > j) dp[i][j] = dp[i-1][j]; 	//大于背包容量直接继承 
            else dp[i][j] = max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);
        }
    return dp[n][C];
}
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n,C;
        cin >> n >> C;
        for(int i=1;i<=n;i++)
            cin >> w[i];
        for(int i=1;i<=n;i++)
            cin >> c[i];
        memset(dp,0,sizeof(dp));
        cout << solve(n,C) << '\n';
    }
    return 0;
}

滚动数组–dp空间优化

dp状态方程常常是二维以上的，占用空间多。从状态方程

$dp[i][j] = max(dp[i-1][j-c[i]]+w[i],dp[i-1][j])$ 可以看出， $dp[i][]$ 只与 $dp[i-1][]$ 有关，所以就用新的一行覆盖已经无用的一行(滚动)，只需要两行就够了。

for(int i=1; i<=n; i++}
    for(int j=C; j>=c[i]; j--)
        dp[j] = max( dp[j], dp[j-c[i]] + w[i] );

要注意：$j$ 应该反过来循环，即从后向前覆盖，否则同一个物品可能会被装两次

优化后DP的空间复杂度从 $O(N×C)$ 降低到 $O(C)$

话不多说，来一道题

题目

这道题是分组背包，需要三层循环

代码

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

int dp[101],c[101][101];

void read(int N,int M){
    memset(c,0,sizeof(c));
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            cin >> c[i][j];
}

int solve(int N,int M){
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=N;i++)
        for(int j=M;j>=0;j--)			//j要反向
            for(int k=1;k<=M;k++)
                if(j>=k)
                    dp[j]=max(dp[j],dp[j-k]+c[i][k]);	//滚动数组
    return dp[M];
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int N,M;
    cin >> N >> M;
    while(N || M){
        read(N,M);
        cout << solve(N,M) << '\n';
        cin >> N >> M;
    }
    return 0;
}

完全背包

完全背包是01背包的一种变式，和01背包的区别就是，01背包是每个物品最多选择1次，但完全背包的每个物品可以选择无限次。

完全背包可以这么来描述：我们有$N$种物品和一个容量为$V$的背包。对于第$i$种物品，它的花费是$c_i$，价值是$w_i$，并且每种物品都可选择无限次。题目通常让我们求 在不超过背包总容量的前提下，选择若干件物品放入背包，使得总价值最大。

完全背包的状态转移式开一个维度就可以，我们定义$dp[j]$为容量为$j$时能达到的最大价值。
注意内层循环必须从小到大遍历容量 j，这和01背包的滚动数组优化是相反的。
状态转移方程为：

$$\quad dp[j] = \max(dp[j], dp[j - w_i] + v_i)$$

内层循环必须从小到大的原因是在计算 $dp[j]$ 时，我们需要的$dp[j-w_i]$正是本轮（第$i$个物品）处理过之后的值。正序遍历可以保证当我们计算 dp[j] 时，dp[j-w_i] 已经被本轮更新过，它储存的已经是考虑了第 $i$ 个物品后的最优解。

以下是洛谷P1616，完全背包的模板。

---

P1616 疯狂的采药

题目描述

LiYuxiang 是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是 LiYuxiang，你能完成这个任务吗？

此题和原题的不同点：

$1$. 每种草药可以无限制地疯狂采摘。

$2$. 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！

输入格式

输入第一行有两个整数，分别代表总共能够用来采药的时间 $t$ 和代表山洞里的草药的数目 $m$。

第 $2$ 到第 $(m + 1)$ 行，每行两个整数，第 $(i + 1)$ 行的整数 $a_i, b_i$ 分别表示采摘第 $i$ 种草药的时间和该草药的价值。

输出格式

输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

数据规模与约定

• 对于 $30\%$ 的数据，保证 $m \le 10^3$。
• 对于 $100\%$ 的数据，保证 $1 \leq m \le 10^4$，$1 \leq t \leq 10^7$，且 $1 \leq m \times t \leq 10^7$，$1 \leq a_i, b_i \leq 10^4$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pull = pair<ull,ull>;
using vec = vector<int>;
using vecl = vector<ll>; 
using maii = map<int,int>;
#define pb(x) push_back(x) 
#define eb(x) emplace_back(x)

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t, m;
    cin >> t >> m;
    vector <ll> dp(t+5), c(m+5), w(m+5);
    for(int i=1;i<=m;i++) cin >> c[i] >> w[i];
    dp[0] = 0;
    for(int i=1;i<=m;i++){
        for(ll j=c[i];j<=t;j++){
            dp[j] = max(dp[j], dp[j-c[i]] + w[i]);
        }
    }
    cout << dp[t];
    return 0;
}

---

这里再对比、强调一下01背包和完全背包的内层循环的区别：

• 0-1背包：for (int j = V; j >= w[i]; j--) (逆序)
• 完全背包：for (int j = w[i]; j <= V; j++) (正序)

变式：恰好装满背包

有些题目要求背包必须被恰好装满，而不是“不超过容量”，比如牛客周赛102的E和F题。
这类题的做法：

1. 将$dp[0]$初始化为0，表示什么都不装，价值为0，是起点；其它的初始化为正无穷或负无穷大。

2. 状态转移式前需要加一个判断if(dp[j - w[i]] != -/+ INF)，表示从上一个状态转移到这个状态时，上一个状态一定要是一个可达的、合法的状态(也就是不为初始化的无穷值)，才能进行状态转移。

memset(dp, -0x3f, sizeof(dp));
dp[0] = 0;
for(..;..;..)
    for(..;..;..)
        if (dp[j - w[i]] != -INF) 
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

变式：求方案总数

如果问题是要求装满背包的方案总数，而不是最大价值，那么就需要再变一下。

我们定义状态：$dp[j]$表示装满容量为$j$的背包的方案数。我们初始化$dp[0] = 1$，表示什么都不装只有这一种方案；其余的初始化为0.

$dp[j]$的方案数，应该等于所有可以转移到它的状态的方案数之和。对于第$i$个物品，我们可以用它来构成$j$的容量，那么$dp[j]$就应该加上从$dp[j-w_i]$转移过来的方案数。

$$dp[j] = dp[j] + dp[j - w_i]$$

这里和普通完全背包的区别就是把 max 操作改为了 + 。

状压DP

状压DP是DP的一种优化方法

Hamilton旅行商问题

Hamilton问题是NP问题，没有多项式复杂度的解法，暴力解法复杂度是 $O(n \times n!)$ ，而状压DP可将复杂度将为 $O(n^2 \times 2n)$

设 $S$ 为图的一个子集；

$dp[S][j]$ ：表示“集合 $S$ 内的最短Hamilton路径”，即从起点 $0$ 出发经过 $S$ 中所有点，到达终点 $j$ 时的最短路径；集合 $S$ 中包括 $j$ 点；

让 $S$ 从最小的子集逐步拓展到整个图，最后得到的 $dp[N][n-1]$ 就是答案， $N$ 表示包含图上所有点的集合。

（ $S-j$ 表示从集合 $S$ 中去掉 $j$ ，即不包含 $j$ 点的集合）

设 $k$ 为 $S-j$ 中一个点，把从 $0$ 到 $j$ 的路径分为两部分：$(0 \rightarrow \dots \rightarrow k)+(k \rightarrow j)$ 。以 $k$ 为变量枚举 $S-j$ 中所有的点，找出最短路径

状态转移方程为：

$$dp[S][j] = min(dp[S-j][k] + dist(k,j))$$

状态压缩DP的技巧：用一个二进制数表示集合 $S$ ，即把 $S$ 压缩到一个二进制数中， $S$ 的每一位表示图上的一个点， $0$ 表示不包含， $1$ 表示包含

例如 $S = 0000 0101$ ，表示包含 $2，0$ 这两个点

if((S>>j) & 1)，判断当前的集合 $S$ 中是否含有 $j$ 点

if((S^(1<<j))>>k & 1) ,其中S^(1<<j)的作用是从集合中去掉 $j$ 点，得到集合 $S-j$ ，然后>> k & 1表示用 $k$ 遍历集合中的 $1$ ，这些 $1$ 就是 $S-j$ 中的点，这样就实现了"枚举集合 $S-j$ 中所有的点" (S^(1<<j))也可以写成S-(1<<j)

Code

#include <bits/stdc++.h>
using namespace std;
int n,dp[1<<20][21];
int dist[21][21];

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    memset(dp,0x3f,sizeof(dp));		//初始化最大值 
    cin >> n;
    for(int i=0;i<n;i++)            //输出图 
        for(int j=0;j<n;j++) 
            cin >> dist[i][j];		//输入点之间的距离 
    dp[1][0] = 0;            //开始：集合中只有点0，起点和终点都是0 
    for(int S=1;S<(1<<n);S++)    //从小集合拓展到大集合，集合用S的二进制表示 
        for(int j=0;j<n;j++)	//枚举点j 
            if((S>>j) & 1)		//这个判断和下面的判断同时起作用 
                for(int k=0;k<n;k++)	//枚举到达j的点k，k属于集合S-j 
                    if((S^(1<<j)) >> k & 1)	//k属于集合S-j 
                        dp[S][j] = min(dp[S][j],dp[S^(1<<j)][k] + dist[k][j]);
    cout << dp[(1<<n)-1][n-1] << '\n';    //终点是n-1； 
    return 0;
}

树形DP

首先是树的储存，树的储存是图的储存的特殊情况，可以用邻接表储存，或链式向前星

二叉苹果树

洛谷P2015

定义状态 $dp[u][j]$ 表示以节点 $u$ 为根的子树上留 $j$ 条边时的最多苹果数量。 $dp[1][q]$ 就是答案。

状态转移方程:

$$dp[u][j] = max(dp[u][j], dp[u][j-k-1] + dp[v][k] + w)$$

其中，$v$ 是 $u$ 的一个子节点。 $dp[u][j]$ 的计算分以下两部分：

1. $dp[v][k]$ ：在 $v$ 上留 $k$ 条边
2. $dp[u][j-k-1]$ ：除了 $v$ 上的 $k$ 条边，以及 $u-v$ 边，那么以u为根的这棵树上还有 $j-k-1$ 条边，它们在 $u$ 的其他子节点上

总复杂度小于 $O(n^3)$

PS：

1. 这道题是无向图储存，因为题目没有说明输入的两个节点哪个是爹哪个是儿，所以要push_back两次，然后在搜的时候跳过father
2. $j$ 循环必须递减，例如 $dp[u][5]$ 会用到 $dp[u][4]$ 和 $dp[u][3]$ 等等，若是递减循环，先算 $5$ ，再算 $4$ ，再算 $3$ $\ldots$ $dp[u][5]$ 用到的是 $dp[u][4]$ 和 $dp[u][3]$ 的原值；若是递增循环， $dp[u][5]$ 就会用到 $dp[u][4]$ 和 $dp[u][3]$ 的新计算后的值，就不对了。

#include <bits/stdc++.h>
using namespace std;
const int N = 200;
int n,q;
int dp[N][N], sum[N];    //sum[i]记录以[i]为根的子树的总边数

struct node{
    int v,w;			//v是子节点，w是边u-v的权值
    node(int a,int b) : v(a),w(b) {}
};
vector <node> e[N];

void dfs(int u,int father){
    for(auto i:e[u]){	//用i遍历u的所有子节点
        if(i.v == father) continue;	//不回头搜父亲，避免循环
        dfs(i.v,u);	//递归到最深的叶子节点，然后返回
        sum[u] += sum[i.v]+1;	//子树上的总边数
        /*两个for循环这样写简单，就是没有优化
        for(int j=sum[u];j>=0;j--)
            for(int k=0;k<=j-1;k++)
        */
        for(int j=min(q,sum[u]);j>=0;j--)
            for(int k=0;k<=min(sum[i.v],j-1);k++)
                dp[u][j] = max(dp[u][j], dp[u][j-k-1] + dp[i.v][k] + i.w);
    }
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> q;
    for(int i=1;i<n;i++){
        int u,v,w;
        cin >> u >> v >> w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});	//无向边
    }
    dfs(1,0);
    cout << dp[1][q];
    return 0;
}

没有上司的舞会

典，上图

这题和上题有点区别

这题没有定义结构体，因为这题是有向无权图，题目已经表明了输入的节点中哪个是爹哪个是儿，而且没有边上没有权值。

定义状态 $dp[u][0]$ 表示不选择当前节点的最优解， $dp[u][1]$ 表示选择当前节点的最优解。

状态转移方程：

$$dp[u][1] += dp[v][0]$$

表示选择该节点，就累加上不选子节点的最大值

$$dp[u][0] += max(dp[v][0], dp[v][1])$$

表示不选该节点，子节点可选可不选

#include <bits/stdc++.h>
using namespace std;
const int N = 6666;
int n, dp[N][2], w[N], father[N];
vector <int> e[N];

void dfs(int u){
    dp[u][0] = 0;
    dp[u][1] = w[u];
    for(auto v:e[u]){
        dfs(v);
        dp[u][1] += dp[v][0];
        dp[u][0] += max(dp[v][0], dp[v][1]);
    }
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++) cin >> w[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin >> v >> u;
        e[u].push_back(v);
        father[v] = u;
    }
    int t = 1;
    while(father[t]) t = father[t];
    dfs(t);
    cout << max(dp[t][0], dp[t][1]) << '\n';
    return 0;
}

区间DP

石子合并

以一道模板题目为例----石子合并

不能用贪心，会陷入局部最优解。用DP求解

定义 $dp[i][j]$ 为合并第 $i$ 堆到第 $j$ 堆的最小花费

状态转移方程为：

$$dp[i][j] = min(dp[i][k] + dp[k+1][j] + w[i][j])，\ i \leq k < j$$

$w[i][j]$ 表示第 $i$ 堆到第 $j$ 堆的石子总数，可以用前缀和计算。$dp[1][n]$ 就是答案

复杂度 $O(n^3)$ ，可以用四边形不等式优化到 $O(n^2)$

自顶向下的思路：

计算大区间 $[i,j]$ 的最优值时，合并它的两个子区间 $[i][k]$ 和 $[k+1][j]$，对所有可能的合并 $(i \leq k < j)$ 采取最优合并。子区间再分解为更小的区间，最小区间 $[i,i+1]$ 只包含两堆石子

自底向上的编程：

先在小区间进行DP得到最优解，再逐步合并小区间为大区间。以下是code：

const int INF = 0x3f3f3f3f;
int dp[n][n] {};    //C++11特性，集成初始化为0

for(int len = 2; len <= n; len++){    //len为i到j的区间长度
    for(int i = 1; i <= n - len + 1; i++){    //区间起点i
        int j = i + len - 1;    //区间终点j
        dp[i][j] = INF;        //初始化为INF
        for(int k = i; k < j; k++){
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]);
        }
    }
}

字符串区间

大致题意：两个长度相等的小写字母字符串 $A$ 和 $B$ 。定义一次操作：把 $A$ 的一个连续子串（区间）都转换为某个字符串（就像用刷子刷成一样的字符）。要把 $A$ 转换成 $B$ ，所需最少操作数是多少？ $strlen \leq 100$

---

input：

zzzzzfzzzzz

abcdefedcba

output:

6

---

两部分dp：1.从空白串转换到 $B$ 。2.从 $A$ 转换到 $B$

1. 从空白串转换到 $B$ ：

① $B[i] == B[j]$ ，原区间 $[i,j]$ 的最少操作次数 等于 分别去掉两个端点的区间的最少操作次数，例如 $B = abbba$ ，最少刷两遍，第一遍刷 $aaaaa$ ，第二遍刷 $bbb$ ；去掉头变为 $bbba$ ，也要刷两遍；去掉尾变 $abbb$ ，也要刷两遍。

② $B[i] \not= B[j]$ ，用标准的区间操作，把区间分为 $[i,k]$ 和 $[k+1,j]$ 两部分来dp

2. 从A转换到B

① $A[j] == B[j]$ ，不用转换，有 $dp[1][j] = dp[1][j-1]$

② $A[j] \not= B[j]$ ，用标准的区间操作，把区间分为 $[i,k]$ 和 $[k+1,j]$ 两部分来dp；这里利用了从空白串转化为 $B$ 的结果，当区间 $[k+1,j]$ 内的A和B字符不同时，从A转化到B与从空白串转化到B是一样的

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;

int dp[102][102];
string a,b;

void solve(const int& n){
    for(int len=2;len<=n;len++){
        for(int i=1;i<=n-len+1;i++){
            int j = i+len-1;
            dp[i][j] = inf;
            if(b[i] == b[j])
                dp[i][j] = dp[i+1][j];
            else for(int k = i;k < j;k++)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
        }
    }
    for(int j=1;j<=n;j++){
        if(a[j] == b[j])
            dp[1][j] = dp[1][j-1];
        else for(int k=1;k<j;k++)
            dp[1][j] = min(dp[1][j], dp[1][k] + dp[k+1][j]);
    }
    cout << dp[1][n] << '\n';
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    while(cin >> a && cin >> b){
        int n = a.size();	
        a = ' ' + a;
        b = ' ' + b;
        for(int i=1;i<=n;i++) dp[i][i] = 1;
        solve(n);
    }
    return 0;
}