C++算法之旅、06 基础篇 | 第四章 动态规划 详解

常见问题

闫式DP分析法

  • 状态表示
    • 集合
      • 满足一定条件的所有方案
    • 属性
      • 集合(所有方案)的某种属性(Max、Min、Count等)
  • 状态计算(集合划分)
    • 如何将当前集合划分成多个子集合

状态计算相当于集合的划分:把当前集合划分成若干个子集,使得每个子集的状态可以先算出来,从而推导当前集合状态(曲线救国


集合划分规则:不重,不漏

特殊情况:属性是 MAX、MIN 的时候,划分的集合是可以重复的

举个例子 A、B、C,先求A、B的最大值,然后求B、C的最大值,最后求两个最大值的最大值,依旧是A、B、C的最大值。例题 ⭐ 897 最长公共子序列


时间复杂度

状态表示数量 * 状态计算量(转移计算量)


如完全背包问题,假定 N 件物品,物品最低体积为 1,背包最大体积容量 V

朴素二维情况:状态表示数量就是 \(NV\),状态计算量就是物品体积为 1 的时候(最坏情况),最内层循环最多需计算 V 次,时间复杂度\(O(NV^2)\)


状态转移路径

DP本质是在一个拓扑图内找最短路

每个状态\(f(i,j)\)看作一个状态的转移看作一条,把状态的值理解为最短路径长

更新最短路的规则是根据题目来的,如完全背包规则 \(f(i,j)=Max(f(i-1,j-k*v[i])+k*w[i])\)

DP结束最终会把从 初始状态(起点)目标状态 (终点)最短路径长 更新出来(生成了一颗最短路径树)

那么 DP求状态转移路径 就变成了在 拓扑图 中找 最短路径 的问题了,沿用 最短路 输出路径的方法就可以找出 状态的转移


方案总结循环dfs 均可实现

  1. 逆推:获取最终状态,根据 最短路规则 逆序往前推,直到 起始状态 ,逐一输出每个状态
  2. 边转移边记录:状态转移过程中,记录每一条边,再利用递推的栈机制,后序输出

注意的点:

  • 因为需要记录路径,状态转移方程可能不好被维度优化,具体问题具体分析
  • 边转移边记录一般需要开一个与状态表示一致维度的数组,要存储每个状态是从上一层哪一状态转移过来的;逆推不需要一致,具体可看下题(保存每组从前组的哪个状态转移过来,一维)

来看一道分组背包题1013 机器分配,要求输出每组选择了哪个物品,我给的题解是第一种方案的循环版本

从终点状态逆推,必定有一条边满足最短路规则,记录当前边,并减去当前组物品的体积,接着开始推前一组状态,直到起始状态

int j = m;
for (int i = n; i; i--) {
    for (int k = 0; k <= j; k++) {
        if (f[i][j] == f[i - 1][j - k] + w[i][k]) {
            path[i] = k;
            j -= k;
            break;
        }
    }
}

可改写成 dfs 的版本

void dfs(int i, int j) {
    if (!i) return;
    for (int k = 0; k <= j; k++) {
        if (f[i - 1][j - k] + w[i][k] == f[i][j]) {
            path[cnt++] = k;
            dfs(i - 1, j - k);
            return;
        }
    }
}

也可用第二种方案,边转移边记录(辅助下标 cnt 就不需要了)

for (int i = 1; i <= n; i++)
    for (int j = 0; j <= m; j++) {
        for (int k = 0; k <= j; k++) {
            int temp = max(f[i][j], f[i - 1][j - k] + w[i][k]);
            if (temp == f[i - 1][j - k] + w[i][k])
                path[i][j] = max(path[i][j], k);

            f[i][j] = temp;
        }
    }

cout << f[n][m] << endl;

输出既可以循环输出(倒着输出),也可以 dfs 逆序输出(正着输出)

void dfs(int i, int j) {
    if (!i) return;
    int k = path[i][j];
    dfs(i - 1, j - k);
    cout << i << " " << k << endl;
}

int j = m;
for (int i = n; i >= 1; i--) {
    cout << i << " " << path[i][j] << endl;
    j -= path[i][j];
}

背包问题初始化

变量声明

一定要根据状态表示的含义,来声明所需变量

如分组背包题 1013 机器分配,最多 10 组,每组 15 个物品,那么定义的常数 N、M 分别表示状态中每维的最大数量(多申请一点)

path 数组用于边转移边记录路径,理所应当和 f 数组是一致维度的大小;写成 path[N][N] 一直找不出问题的屑。


状态初始化

本篇内容只涉及了 至多、恰好 两种情况的问,至少 情况将在提高篇提及

关于 f[0] = 1 的解释,请看 278 01背包 计数

求方案数
二维情况
1、体积至多j,f[0][i] = 1, 0 <= i <= m,其余是0
2、体积恰好j,f[0][0] = 1, 其余是0

一维情况
1、体积至多j,f[i] = 1, 0 <= i <= m,
2、体积恰好j,f[0] = 1, 其余是0

求最大值最小值
二维情况
1、体积至多j,f[i,k] = 0,0 <= i <= n, 0 <= k <= m(只有求最大值题型)
2、体积恰好j,
求最小值:f[0][0] = 0, 其余是INF
求最大值:f[0][0] = 0, 其余是-INF

一维情况
1、体积至多j,f[i] = 0, 0 <= i <= m(只有求最大值题型)
2、体积恰好j,
求最小值:f[0] = 0, 其余是INF
求最大值:f[0] = 0, 其余是-INF

下标从1开始

如果状态转移涉及 \(i-1\) 层,DP问题下标最好从1开始(如第一个物品的下标是1),这是经验,基本上所有DP题目都是这样


递归

所有DP问题都可以改用递归,如 285 没有上司的舞会 901 滑雪


背包DP

01背包

\(N\) 个物品,\(V_i\) 表示体积,\(W_i\) 表示价值,每件物品只有一个。求背包装得下的情况下的最大价值多少

  • 状态表示 \(f(i,j)\)
    • 集合
      • 只考虑前 \(i\) 个物品,且总体积不大于 \(j\) 的所有选法
    • 属性
      • \(max\) (每个选法的总价值的最大值)
  • 状态计算
    • 不含 \(i\) 的选法 集合,相当于 \(f(i-1,j)\)
    • \(i\) 的选法 集合,相当于 \(f(i-1,j-V_i) + W_i\)
      • 由于所有选法都包含第 \(i\) 物品,所以先把第 \(i\) 物品去掉,然后求最大值,然后再把第 \(i\) 物品加上
      • 可能是空集 \(j < V_i\),朴素代码中需要做判断
    • 转移方程 \(f(i,j) = max(f(i-1,j),f(i-1,j-V_i) + W_i)\)满足 \(V_i <= j\)

朴素、二维

2. 01背包问题 - AcWing题库

#include <algorithm>
#include <iostream>

using namespace std;

int const N = 1e3 + 10;
int n, m;
int v[N], w[N];
int f[N][N];  // f[0][0~m] 默认都是0;1件物品都没选

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            // 把下面两行代码合并到一起看
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

优化、一维

  • \(f(i)\)只用到了\(f(i-1)\)这一层,可以用滚动数组来做
  • \(j\) 当做一维数组下标位置,如果从小到大枚举体积,会覆盖上一层数据,因此从大到小枚举体积,另外可以限制 \(j\) 遍历到 \(v[i]\) 停止,这样省了判断语句
#include <algorithm>
#include <iostream>

using namespace std;

int const N = 1e3 + 10;
int n, m;
int v[N], w[N];
int f[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[m] << endl;
    return 0;
}

完全背包

\(N\) 个物品,\(V_i\) 表示体积,\(W_i\) 表示价值,每件物品无限多个。求背包装得下的情况下的物品最大价值多少

  • 状态表示 \(f(i,j)\)
    • 集合
      • 只考虑前 \(i\) 个物品,且总体积不大于 \(j\) 的所有选法
    • 属性
      • \(max\) (每个选法的总价值的最大值)
  • 状态计算
    • 按第 \(i\) 个物品选多少个划分
    • 0个:\(f(i-1,j)\)
    • k个:\(f(i-1,j-k*v[i])+k*w[i]\)
      • 去掉 \(k\) 个物品 \(i\) 的体积
      • \(f(i-1,j-k*v[i])\)
      • 加上 \(k\) 个物品 \(i\) 的价值
    • 转移方程 \(f(i,j)=f(i-1,j-k*v[i])+k*w[i]\)满足 \(k*v[i]<=j\)

朴素、二维

3. 完全背包问题 - AcWing题库

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1e3 + 10;

int n, m;
int v[N], w[N];
int f[N][N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k * v[i] <= j; k++)
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);

    cout << f[n][m] << endl;
    return 0;
}

优化、二维

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1e3 + 10;

int n, m;
int v[N], w[N];
int f[N][N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++) {
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }

    cout << f[n][m] << endl;
    return 0;
}

优化、一维

01背包、完全背包有相似之处

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1e3 + 10;

int n, m;
int v[N], w[N];
int f[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++)
        for (int j = v[i]; j <= m; j++) { // 区别只在这
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }

    cout << f[m] << endl;
    return 0;
}

优化重点

01背包和完全背包一维优化的不同点在状态转移方程上

  • 如果用上一层状态就要从大到小枚举体积(01背包二维转一维)
  • 如果用本层状态就要从小到大枚举体积(完全背包二维转一维)

多重背包

\(N\) 个物品,\(V_i\) 表示体积,\(W_i\) 表示价值,每件物品\(X_i\)。求背包装得下的情况下的物品最大价值多少

  • 状态表示 \(f(i,j)\)
    • 集合
      • 只考虑前 \(i\) 个物品,且总体积不大于 \(j\) 的所有选法
    • 属性
      • \(max\) (每个选法的总价值的最大值)
  • 状态计算
    • 转移方程 \(f(i,j) = max(f(i-1,j-v[i] * k)+w[i]*k),k\in[0,X_i]\)满足 \(k*v[i]<=j\)

朴素、二维

4. 多重背包问题 I - AcWing题库

#include <algorithm>
#include <iostream>

using namespace std;

int const N = 1e2 + 10;

int n, m;
int v[N], w[N], x[N];
int f[N][N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> x[i];

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k <= x[i] && k * v[i] <= j; k++)
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
    cout << f[n][m];
    return 0;
}

优化、一维⭐

二进制法,将 \(X_i\) 拆分成 \(\lceil log_2X_i \rceil\) 个物品(\(1,2,4,8,16,...,2^k,C\)),将多重背包转变成01背包问题

#include <algorithm>
#include <iostream>

using namespace std;

int const N = 1000 * 11 + 10;
int n, m;
int v[N], w[N];
int f[N];

int main() {
    cin >> n >> m;

    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        int a, b, x;
        cin >> a >> b >> x;
        int k = 1;
        while (k <= x) {
            cnt++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            x -= k;
            k *= 2;
        }
        if (x > 0) {  // 若 x 还有剩余
            cnt++;
            v[cnt] = a * x;
            w[cnt] = b * x;
        }
    }
    n = cnt;

    for (int i = 1; i <= n; i++)
        for (int j = m; j >= v[i]; j--) f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}

究极、单调队列⭐

分析问题

6. 多重背包问题 III - AcWing题库

\(\begin{array}{l} 0<N \leq 1000 \\ 0<V \leq 20000 \\ 0<v_{i}, w_{i}, s_{i} \leq 20000 \end{array}\)

这种情况下,采用转01背包法,时间复杂度是 \(1000 * log_220000*20000\) = 1.4e4 + 2e4 = 3e8,肯定会TLE


单调队列

先认识一下单调队列是什么 C++算法之旅、05 基础篇 | 第二章 数据结构 - 小能日记

https://leetcode.cn/problems/sliding-window-maximum

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
   public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        int q[nums.size()];
        memset(q, 0, sizeof q);
        int hh = 0, tt = -1;
        for (int i = 0; i < nums.size(); i++) {
            while (hh <= tt && q[hh] < i - k + 1) hh++;
            while (hh <= tt && nums[q[tt]] <= nums[i]) tt--;
            q[++tt] = i;  // 插入位置
            if (i + 1 >= k) res.push_back(nums[q[hh]]);
        }

        return res;
    }
};

解决问题

先来看多重背包的朴素二维代码

for (int i = 1; i <= n; i++)
    for (int j = 0; j <= vt; j++)
        for (int k = 0; k <= s[i] && k * v[i] <= j; k++) {
            f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
        }

可以这样优化,遍历每个物品,然后总体积 \(j\) 分为 \(r\) 类 (\(r = v[i] - 1\))。选择其中一类,如第 \(r\) 类,那么从 \(r\) 遍历到 \(vt\) 的过程,即 int j = r; j <= vt; j += v[i] 这一过程,由于物品数量是有限的,相当于维护了一个固定宽度的滑动窗口,\(j\) 每移动一次,对滑动窗口做出滑动、删除、插入、选择四个操作,滑动窗口用单调队列实现,每个物体只需遍历一遍\([0,vt]\),原先的 \(k\) 循环被优化掉了,时间复杂度变为 \(O(NV)\)

  • \(w[i]\) 个数,即队内元素 \(j'\) 与当前 \(j\) 的差值 除以 \(v[i]\);也意味着选择了几个 \(i\) 物品
  • 滑动:队头元素是否出界;也就是 \(w[i]\) 的个数 > \(s[i]\) ,选择了大于 \(s[i]\) 个物品
  • 删除:维持单调队列特性;判断队尾每个 \(j'\) 对应的属性值是否 <= \(j\) 当前对应的属性值,True就删除
    • 对应的值计算公式 f[i - 1][q[tt]] + (j - q[tt]) / v[i] * w[i]
  • 插入:将当前 \(j\) 插入队尾
  • 选择:从队头取出 \(j'\) ,对应的属性值就是 \(f(i,j)\) 的最大值(滑动窗口 \(s[i]\) 项里面选择最大一项
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

int const N = 1e3 + 10, M = 2e4 + 10;

int n, vt;
int v[N], w[N], s[N];
int f[N][M];
int q[M];

int main() {
    cin.tie(0);
    cin >> n >> vt;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];

    for (int i = 1; i <= n; i++) {
        for (int r = 0; r < v[i]; r++) {
            int hh = 0, tt = -1;
            for (int j = r; j <= vt; j += v[i]) {
                // 滑动
                if (hh <= tt && (j - q[hh]) / v[i] > s[i]) hh++;
                // 删除
                while (hh <= tt &&
                       f[i - 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <=
                           f[i - 1][j])
                    tt--;
                // 插入
                q[++tt] = j;
                // 选择
                f[i][j] = f[i - 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
            }
        }
    }

    cout << f[n][vt];
    return 0;
}

优化代码①

循环已经减少了一层,但空间依旧需要\(O(NV)\),学着01背包优化的思路,用滚动数组优化一下代码,由于滑动的方向不可变,不能修改 for 循环里的 j,可以将相邻两层状态保存到 f 数组中 f[2][M]

  • (i - 1) & 1 就是上一层
  • i & 1 就是当前层
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

int const N = 1e3 + 10, M = 2e4 + 10;

int n, vt;
int v[N], w[N], s[N];
int f[2][M];
int q[M];

int main() {
    cin.tie(0);
    cin >> n >> vt;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];

    for (int i = 1; i <= n; i++) {
        for (int r = 0; r < v[i]; r++) {
            int hh = 0, tt = -1;
            for (int j = r; j <= vt; j += v[i]) {
                // 滑动
                if (hh <= tt && (j - q[hh]) / v[i] > s[i]) hh++;
                // 删除
                while (hh <= tt &&
                       f[(i - 1) & 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <=
                           f[(i - 1) & 1][j])
                    tt--;
                // 插入
                q[++tt] = j;
                // 选择
                f[i & 1][j] = f[(i - 1) & 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
            }
        }
    }

    cout << f[n & 1][vt];
    return 0;
}

优化代码②

不用滚动数组也可以,声明一个跟 f[M] 同等大小的数组 backup[M],用于保存上一个物品 i 的所有状态。新一层循环每次都把上一层循环的 f 数组拷贝到 backup 数组中,这样新一层 i 就可以用到上一层 i 的状态了

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

int const N = 1e3 + 10, M = 2e4 + 10;

int n, vt;
int v[N], w[N], s[N];
int f[M], backup[M];
int q[M];

int main() {
    cin.tie(0);
    cin >> n >> vt;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];

    for (int i = 1; i <= n; i++) {
        memcpy(backup, f, sizeof f);
        for (int r = 0; r < v[i]; r++) {
            int hh = 0, tt = -1;
            for (int j = r; j <= vt; j += v[i]) {
                // 滑动
                if (hh <= tt && (j - q[hh]) / v[i] > s[i]) hh++;
                // 删除
                while (hh <= tt &&
                       backup[q[tt]] + (j - q[tt]) / v[i] * w[i] <= backup[j])
                    tt--;
                // 插入
                q[++tt] = j;
                // 选择
                f[j] = backup[q[hh]] + (j - q[hh]) / v[i] * w[i];
            }
        }
    }

    cout << f[vt];
    return 0;

分组背包

\(N\) 个分组,每个分组里有\(X\)个物品,\(V_i\) 表示体积,\(W_i\) 表示价值,每组物品里选一个。求背包装得下的情况下的物品最大价值多少

  • 状态表示 \(f(i,j)\)
    • 集合
      • 只考虑\(i\) 组物品,且总体积不大于 \(j\) 的所有选法
    • 属性
      • \(max\) (每个选法的总价值的最大值)
  • 状态计算
    • 不选第 i 组物品、选第 i 组第 1 个物品、选第 i 组第 2 个物品、...选第 i 组最后一个物品
    • 不选第 i 组物品:\(f(i-1,j)\)
    • 选第 i 组物品第 k 个物品:\(f(i-1,j-v[i,k])+w[i,k]\)
      • 可能是空集 \(j < V_{ik}\) ,朴素代码中需要做判断
    • 转移方程 \(f(i,j) = max(f(i-1,j),f(i-1,j-v[i,k])+w[i,k]),k\in [1,X_i]\)满足 \(v[i,k]<=j\)

朴素、二维

#include <algorithm>
#include <iostream>

using namespace std;

int const N = 1e2 + 10;

int n, m;
int v[N][N], w[N][N], x[N];
int f[N][N];

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> x[i];
        // 这里与上面状态转移方程不同,下标从0开始,个人喜好
        for (int j = 0; j < x[i]; j++) { 
            cin >> v[i][j] >> w[i][j];
        }
    }

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++) {
            f[i][j] = f[i - 1][j];
            for (int k = 0; k < x[i]; k++)
                if (v[i][k] <= j)
                    f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
        }

    cout << f[n][m];
    return 0;
}

优化、一维

#include <algorithm>
#include <iostream>

using namespace std;

int const N = 1e2 + 10;

int n, m;
int v[N][N], w[N][N], x[N];
int f[N];

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> x[i];
        for (int j = 0; j < x[i]; j++) {
            cin >> v[i][j] >> w[i][j];
        }
    }

    for (int i = 1; i <= n; i++)
        for (int j = m; j >= 0; j--)
            for (int k = 0; k < x[i]; k++)
                if (v[i][k] <= j) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    cout << f[m];
    return 0;
}

混合背包

物品分类

7. 混合背包问题 - AcWing题库

判断当前物品是哪个类的,然后转移的时候按照各个类的逻辑去转移。本题中的多重背包还可以拆分成 01 背包,所以只需要判断两个类

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

int const N = 1e3 + 10;

int n, vt;
int f[N];

struct Thing {
    int kind;
    int v, w;
};
vector<Thing> things;

int main() {
    cin >> n >> vt;
    // 分类
    for (int i = 0; i < n; i++) {
        int v, w, s;
        cin >> v >> w >> s;
        if (s < 0)
            things.push_back({-1, v, w});
        else if (s == 0)
            things.push_back({0, v, w});
        else {
            for (int k = 1; k <= s; k *= 2) {
                s -= k;
                things.push_back({-1, v * k, w * k});
            }
            if (s > 0) things.push_back({-1, v * s, w * s});
        }
    }
    for (auto thing : things) {
        if (thing.kind < 0) {
            for (int j = vt; j >= thing.v; j--) {
                f[j] = max(f[j], f[j - thing.v] + thing.w);
            }
        } else if (thing.kind == 0) {
            for (int j = thing.v; j <= vt; j++) {
                f[j] = max(f[j], f[j - thing.v] + thing.w);
            }
        }
    }
    cout << f[vt] << endl;
    return 0;
}

二维费用

体积重量

8. 二维费用的背包问题 - AcWing题库

涉及到了体积与重量,将原先01背包优化后的 \(f(i)\) 变成 \(f(i,j)\)

  • \(f(i)\) 总体积不超过 \(i\) 的最大价值
  • \(f(i,j)\) 总体积不超过 \(i\) 且总重量不超过 \(j\) 的最大价值

时间复杂度 \(O(NVM)\);因为要用到上一层状态,所以是 \(i,j\) 都是从大到小枚举;读入物品信息和更新一层状态可以放在一起进行

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

int const N = 110;

int n, m, v;
int f[N][N];

int main() {
    cin >> n >> v >> m;
    for (int i = 0; i < n; i++) {
        int vx, mx, wx;
        cin >> vx >> mx >> wx;
        for (int j = v; j >= vx; j--) {
            for (int k = m; k >= mx; k--) {
                f[j][k] = max(f[j][k], f[j - vx][k - mx] + wx);
            }
        }
    }
    cout << f[v][m];
    return 0;
}

方案计数⭐

朴素、二维

11. 背包问题求方案数 - AcWing题库

  • 状态表示 \(g(i,j)\)
    • 集合
      • 考虑前 \(i\) 件物品,总体积恰好为 \(j\),且总价值最大的所有选法
    • 属性
      • \(count\)
  • 状态计算
    • 选 i 的价值的是最大的
      • \(g(i,j)=g(i-1,j-v)\)
    • 不选 i 的价值是最大的
      • \(g(i,j)=g(i-1,j)\)
    • 选 i 和不选 i 的价值都是最大的
      • \(g(i,j)=g(i-1,j-v)+g(i-1,j)\)

如何判断状态计算的三种情况:根据已更新完的 \(f(i,j)\) 来判断,举个例子,如果 \(f(i,j)\)\(f(i-1,j)\) 转移过来,那可能就是(不选 i ,选 i 和不选 i )这两种情况,接着判断就行

g 数组更新完后需要遍历最后一层与最大总价值\(f(i,j)\)相同的各项:即考虑前 i 个物品,总体积恰好为 \([0,j]\)最大总价值的方案数的和

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e3 + 10;
int v[N], w[N];
int f[N][N];
int g[N][N];
int n, vt;
int mod = 1e9 + 7;

int main() {
    cin >> n >> vt;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= vt; j++) {
            f[i][j] = f[i - 1][j];
            if (v[i] <= j) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    }

    g[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= vt; j++) {
            if (f[i][j] == f[i - 1][j]) g[i][j] = (g[i][j] + g[i - 1][j]) % mod;
            if (v[i] <= j && f[i][j] == f[i - 1][j - v[i]] + w[i])
                g[i][j] = (g[i][j] + g[i - 1][j - v[i]]) % mod;
        }
    }
    int res = 0;
    for (int j = 0; j <= vt; ++j) {
        if (f[n][j] == f[n][vt]) {
            res = (res + g[n][j]) % mod;
        }
    }
    cout << res << endl;
    return 0;
}

优化、一维

可以发现 g 数组的更新都是根据 f 数组状态更新的路径来的,两个循环可以放在一块。同时可以用一维数组优化

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e3 + 10;
int v[N], w[N];
int f[N];
int g[N];
int n, vt;
int mod = 1e9 + 7;

int main() {
    cin >> n >> vt;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    g[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = vt; j >= v[i]; j--) {
            int temp = max(f[j], f[j - v[i]] + w[i]), c = 0;
            if (temp == f[j]) c = (c + g[j]) % mod;
            if (temp == f[j - v[i]] + w[i]) c = (c + g[j - v[i]]) % mod;
            f[j] = temp, g[j] = c;
        }
    }

    int res = 0;
    for (int j = 0; j <= vt; ++j) {
        if (f[j] == f[vt]) {
            res = (res + g[j]) % mod;
        }
    }
    cout << res << endl;
    return 0;
}

方案记录

12. 背包问题求具体方案 - AcWing题库

所有背包问题都可以把方案数出来,相当于求状态转移路径,本题的难点在于字典序输出

针对第一个物品选择有三种情况,后续物品也按这个思路考虑

  • 只能选,必选
  • 只能不选,必不选
  • 可选可不选,必选(保证题目要求的字典序)

原来的背包DP是从 1 推到 n,从 n 逆推的时候并不能保证字典序,况且可能有多个物品选择方式(看看方案计数问题

所以需要倒过来从 n 推到 1,此时 \(f(1,m)\) 就是最大总价值,就可以从 1 开始逆推了

#include <bits/stdc++.h>

using namespace std;

int const N = 1e3 + 10, V = 1e3 + 10;
int n, vt;
int v[N], w[N];
int f[N][V];
int path[N], cnt;

int main() {
    cin >> n >> vt;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j <= vt; j++) {
            f[i][j] = f[i + 1][j];
            if (v[i] <= j) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
        }
    }
    // f[1][m] 最大值

    int j = vt;
    for (int i = 1; i <= n; i++)
        if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) {
            cout << i << ' ';
            j -= v[i];
        }

    return 0;
}

练习题

278 01背包 计数

278. 数字组合 - AcWing题库

  • 状态表示 \(f(i,j)\)
    • 集合
      • 考虑前 \(i\) 个物品,总体积恰好等于 \(j\) 的选法集合
    • 属性
      • \(count\)
  • 状态计算
    • 不选第 i 物品的所有方案:\(f(i-1,j)\)
    • 选择第 i 物品的所有方案:\(f(i-1,j-V_i)\)
    • 转移方程:\(f(i,j) = f(i-1,j) + f(i-1,j-V_i)\)

f[0] = 1 含义

f[0] = 1; 表示从前 0 个物品选出总体积为 0 的方案数为 1;一个物品都不选,此时总体积为0,这也是一种合法的方案

二维写法,即 \(f(i,0) = 0 , i \in [0,n]\),表示从前 \(i\) 个物品选出总体积为 0 的方案数为 1

如计算转移的状态 \(f(i-1,j-s*V_i)\) 中,如果恰好 \(j-s*V_i =0\),代表恰好 \(s\)\(i\) 物品能够满足 \(j\) 的要求,此时是一种合法的方案


题解

#include <algorithm>
#include <iostream>

using namespace std;

int const N = 1e2 + 10, M = 1e4 + 10;

int n, m;
int v[N];
int f[M];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i];

    f[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= v[i]; j--) {
            f[j] = f[j] + f[j - v[i]];
        }

    cout << f[m];
    return 0;
}

423 01背包 Max

423. 采药 - AcWing题库

\(f(i,j)\)考虑前 \(i\) 个草药,采集时间不超过 \(j\) 的所有方案的最大总价值

#include <algorithm>
#include <iostream>

using namespace std;

int const N = 1e2 + 10, M = 1e3 + 10;

int n, m;
int v[N], w[N];
int f[M];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> v[i] >> w[i];

    for (int i = 1; i <= m; i++)
        for (int j = n; j >= v[i]; j--) f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[n];
    return 0;
}

426 01背包 Max

426. 开心的金明 - AcWing题库

\(f(i,j)\) 考虑前 \(i\) 个物品,在不超过 \(j\) 元的情况下,所有方案的价格重要度乘积和的最大值

#include <algorithm>
#include <iostream>

using namespace std;
int const N = 1e2, M = 3e4 + 10;

int n, m;
int v[N], w[N];
int f[M];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> v[i] >> w[i];

    for (int i = 1; i <= m; i++)
        for (int j = n; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + v[i] * w[i]);

    cout << f[n];
    return 0;
}

279 完全背包 计数

279. 自然数拆分 - AcWing题库

  • 状态表示 \(f(i,j)\)
    • 集合
      • 只考虑前 \(i\) 个物品(每个物品若干个),且总体积恰好等于 \(j\) 的所有选法
    • 属性
      • \(count\)
  • 状态计算
    • 不选:\(f(i-1,j)\)
    • 选第 \(i\)\(k\) 件物品:\(f(i-1,j-V_i*k)\)
    • 转移方程 \(f(i,j) = \sum f(i-1,j-V_i*k)\) 满足 \(k*v[i]<=j\)

以下是优化后的写法

#include <algorithm>
#include <iostream>

using namespace std;

int const N = 4e3 + 10;

int n;
unsigned f[N];

int main() {
    cin >> n;

    // 初始化
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            f[j] += f[j - i];
        }
    }

    cout << (f[n] - 1) % 2147483648u << endl;

    return 0;
}

587 完全背包 Min

587. 吃蛋糕 - AcWing题库

  • 状态表示 \(f(i,j)\)
    • 集合
      • 考虑前 \(i\) 个物品,总体积恰好等于 \(j\) 的所有方案
    • 属性
      • \(min\) (每个方案的元素个数)
  • 状态计算
    • 不选第 i 个:\(f(i-1,j)\)
    • 选第 i 个 k 件物品:\(f(i-1,j-V_i*k) + k\)
    • 转移方程 \(f(i,j) = min(f(i-1,j-V_i*k) + k)\)
    • \(f(0,0)\) 为 0(什么都不选元素个数为0);其他 \(f(i,j)\) 全部 INF(Min);物品数量 \(\lfloor sqrt(N) \rfloor\)

朴素写法 (优化写法在后面)

状态数量 \(nlog_2n\) ,状态转移计算 \(n\) 次(实际比n小),时间复杂度 \(O(n^2log_2n)\),会TLE

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

int const N = 1e2, M = 1e4 + 10;

int t, n;
int f[N][M];

int main() {
    cin >> t;
    for (int id = 1; id <= t; id++) {
        cin >> n;
        int m = 1;
        while (m * m <= n) m++;
        m--;
        // 初始化状态
        memset(f, 0x3f, sizeof f);
        f[0][0] = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k * (i * i) <= j; k++) {
                    f[i][j] = min(f[i][j], f[i - 1][j - k * (i * i)] + k);
                }
            }
        }
        cout << "Case #" << id << ": " << f[m][n] << endl;
    }

    return 0;
}

优化写法

for (int i = 1; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            f[i][j] = f[i - 1][j];
            if (i * i <= j) f[i][j] = min(f[i][j], f[i][j - i * i] + 1);
        }
    }
    cout << "Case #" << id << ": " << f[m][n] << endl;
}

一维写法

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

int const N = 1e2, M = 1e4 + 10;

int t, n;
int f[M];

int main() {
    cin >> t;
    for (int id = 1; id <= t; id++) {
        cin >> n;
        memset(f, 0x3f, sizeof f);
        f[0] = 0;
        for (int i = 1; i <= n / i; i++) {
            for (int j = i * i; j <= n; j++) {
                f[j] = min(f[j], f[j - i * i] + 1);
            }
        }
        cout << "Case #" << id << ": " << f[n] << endl;
    }

    return 0;
}

1013⭐分组背包

1013. 机器分配 - AcWing题库

将每个公司当做物品组,如第一个公司(物品组)包括三个物体(分一台、分两台、分三台)

  • \(i\) 公司第 \(k\) 件物品

    • 含义:分给第 \(i\) 个公司 \(k\) 台机器
    • 体积:\(k\)
    • 价值:\(w_{ik}\)
  • 状态表示 \(f(i,j)\)

    • 集合
      • 只考虑\(i\) 组物品,且总体积不大于 \(j\) 的所有选法
    • 属性
      • \(max\) (每个选法的总价值的最大值)
  • 状态计算

    • 不选第 i 组物品、选第 i 组第 1 个物品、选第 i 组第 2 个物品、...选第 i 组最后一个物品
    • 不选第 i 组物品:\(f(i-1,j)\)
    • 选第 i 组物品第 k 个物品:\(f(i-1,j-v[i,k])+w[i,k]\)

题目还要求输出每个公司选择了哪个物品,是求状态转移路径问题

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 11, M = 16;
int n, m;
int w[N][M];
int f[N][M];
int way[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> w[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++) {
            // f[i][j] = f[i - 1][j];  // 如果写了下面 k 改成 1
            for (int k = 0; k <= j; k++) {
                f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]);
            }
        }

    cout << f[n][m] << endl;

    int j = m;
    for (int i = n; i; i--) {
        for (int k = 0; k <= j; k++) {
            if (f[i][j] == f[i - 1][j - k] + w[i][k]) {
                way[i] = k;
                j -= k;
                break;
            }
        }
    }

    for (int i = 1; i <= n; i++) cout << i << " " << way[i] << endl;
    return 0;
}

线性DP

递推方程是线性关系(如背包问题二维矩阵,是一行一行来求的)


898 数字三角形

898. 数字三角形 - AcWing题库

  • 状态表示 \(f(i,j)\)
    • 集合
      • 从起点走到\((i,j)\)的所有路径
    • 属性
      • \(max\) (每个路径的长度)
  • 状态计算
    • 来自左上方的一类、来自右上方的一类
    • 来自左上方:\(f(i-1,j-1)+a[i,j]\)
    • 来自右上方:\(f(i-1,j)+a[i,j]\)
    • 转移方程 \(f(i,j) = max(f(i-1,j-1)+a[i,j],f(i-1,j)+a[i,j])\)

状态数量 \(n^2\),转移计算量 \(O(1)\),时间复杂度 \(O(n^2)\)

注意初始化部分,算最右侧点的时候,因为最右点不存在,需要初始化 -INF,左侧点同理

#include <algorithm>
#include <iostream>

using namespace std;

int const N = 5e2 + 10, INF = 1e9;
int a[N][N];
int f[N][N];
int n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++) cin >> a[i][j];
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= i + 1; j++) f[i][j] = -INF;

    f[1][1] = a[1][1];
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= i; j++)
            f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);

    int res = -INF;
    for (int i = 1; i <= n; i++) res = max(res, f[n][i]);
    cout << res;
    return 0;
}

895 最长上升子序列

895. 最长上升子序列 - AcWing题库

  • 状态表示 \(f(i)\)
    • 集合
      • 以序列第 \(i\) 个数(下标位置)结尾的所有上升子序列
    • 属性
      • \(max\) (每个上升子序列的长度)
  • 状态计算
    • \(i\) 个数已确定,根据第 \(i-1\) 个数是序列哪个数(下标位置)来分类
    • \(r = 0(只有 i 自己)、1、2、3...i-1\),前提是 \(a_r < a_i\)
    • 转移方程 \(f(i) = max(f(r) + 1)\)\(a_r < a_i\)\(0 <= r <= i -1\)

状态数量 n,转移数量 n ,故 \(O(n^2)\)

#include <algorithm>
#include <iostream>

using namespace std;

int const N = 1e3 + 10;
int n;
int a[N];
int f[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        f[i] = 1;  // 只有 i 一个数的情况,也就是 j = 0 情况
        for (int j = 1; j < i; j++) {
            if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) res = max(res, f[i]);
    cout << res;
    return 0;
}

如何保存最长序列

用一个数组存储状态的转移

#include <algorithm>
#include <iostream>

using namespace std;

int const N = 1e3 + 10;
int n;
int a[N];
int f[N];
int g[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        f[i] = 1;  // 只有 i 一个数的情况,也就是 j = 0 情况
        g[N] = 0;
        for (int j = 1; j < i; j++) {
            if (a[j] < a[i]) {
                if (f[i] < f[j] + 1) {
                    f[i] = f[j] + 1;
                    g[i] = j;
                }
            }
        }
    }
    int res = 0, last = 0;  // last 标记最长子序列末尾位置
    for (int i = 1; i <= n; i++) {
        if (f[i] > res) {
            res = f[i];
            last = i;
        }
    }
    cout << res << endl;
    cout << "路径" << endl;
    for (int i = 1; i <= res; i++) {
        cout << a[last] << " ";
        last = g[last];
    }
    return 0;
}

896⭐最长上升子序列2

896. 最长上升子序列 II - AcWing题库

贪心。定义一个数组,存储所有不同长度上升子序列结尾的最小值,随长度增加,结尾最小值单调递增。每次插入一个 \(a_i\) 整数二分查找(小于某个数的最大的数),返回长度并更新数组。时间复杂度 \(O(nlog_2n)\)。不是DP做法

#include <algorithm>
#include <iostream>

using namespace std;

int const N = 1e5 + 10;
int n;
int a[N];
int q[N];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    int len = 0;
    q[0] = -2e9;
    for (int i = 0; i < n; i++) {
        int l = 0, r = len;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i])
                l = mid;
            else
                r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }
    cout << len;
    return 0;
}

897 最长公共子序列

897. 最长公共子序列 - AcWing题库

  • 状态表示 \(f(i,j)\)

    • 集合
      • 在第一个序列的前 \(i\) 个字母中出现,且在第二个序列的前 \(j\) 个字母中出现的所有公共子序列
    • 属性
      • max (每个公共子序列的长度 )
  • 状态计算

    • a[i]、b[j] 是否包含在公共子序列当中作为划分依据(四种情况)(不出现和必须出现)

    • 00:\(f(i-1,j-1)\)这一类情况被包含在01 | 10内

    • 01:\(f(i-1,j)\)

      • \(f(i-1,j)\) 包含 01 的情况,求 max 是可以重复的(求数量不能重复)
    • 10:\(f(i,j-1)\),同理

    • 11:\(f(i-1,j-1)+1\)

      • 前提是 a[i] == b[j]

一般只考虑 01、10、11 三种情况。状态数量 \(n^2\) ,状态转移计算 3 次,时间复杂度 \(O(n^2)\)

因为需要从\(i-1\)层开始算,下标从1开始读

#include <algorithm>
#include <iostream>

using namespace std;

int const N = 1e3 + 10;
int n, m;
char a[N], b[N];
int f[N][N];

int main() {
    cin >> n >> m;
    scanf("%s%s", a + 1, b + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

902⭐最短编辑距离

902. 最短编辑距离 - AcWing题库

  • 状态表示 \(f(i,j)\)
    • 集合
      • 将a[1~i]变成b[1~j]的所有操作方案
    • 属性
      • min (每个方案的操作次数)
  • 状态计算:按最后一次操作分类
    • \(f(i-1,j) + 1\)
    • \(f(i,j-1) + 1\)
    • \(f(i-1,j-1) + 1/0\) (看a[i]是否等于b[j])

状态数量 \(n^2\) ,状态转移计算 3 次,时间复杂度 \(O(n^2)\)

https://www.acwing.com/solution/content/5607/


相信很多人都是这么考虑问题的:dp[i][j]为 a 的 [0..i] 转换成 b 的 [0..j] 的最小操作数。

if (删除的情况) dp[i][j] = dp[i-1][j] + 1;
else if (新增的情况) dp[i][j] = dp[i][j-1] + 1; 
else if (修改的情况) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = dp[i-1][j-1]; // 不需要任何操作, 和上一个状态相同

注意,这种考虑方式不需要写 min,因为你准确的描述了各种情况。

这样想其实是没有毛病的,但是难点在于你无法把 () 中的情况准确的用代码表达出来。

能描述出来的只有 不需要操作 这种情况,若 a[i] == b[j] 则无需修改,其余情况难以准确的描述。

但这题其实求的是 最短编辑距离,突出了一个最短,所以以上情况完全可以归纳为:

// 无需操作
if (a[i] == b[j]) dp[i][j] = dp[i-1][j-1];
// 新增, 删除, 修改 都是可以到当前状态的, 我只管取其中最小值就行
else dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

int const N = 1e3 + 10;

int n, m;
char a[N], b[N];
int f[N][N];

int main() {
    // scanf("%d%s", &n, a + 1);
    // scanf("%d%s", &m, b + 1);

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

    cin >> m;
    for (int i = 1; i <= m; i++) cin >> b[i];

    // 初始化 0
    // 只添加
    for (int i = 0; i <= m; i++) f[0][i] = i;
    // 只删除
    for (int i = 0; i <= n; i++) f[i][0] = i;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            if (a[i] == b[j])
                f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            else
                f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
        }
    }
    cout << f[n][m];
    return 0;
}

899 编辑距离

899. 编辑距离 - AcWing题库

注意下标从 1 开始

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 15, M = 1e3 + 10;
int n, m;
int f[N][N];
char str[M][N];

int edit_distance(char a[], char b[]) {
    int la = strlen(a + 1), lb = strlen(b + 1);
    for (int i = 0; i <= lb; i++) f[0][i] = i;
    for (int i = 0; i <= la; i++) f[i][0] = i;
    for (int i = 1; i <= la; i++) {
        for (int j = 1; j <= lb; j++) {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }
    }
    return f[la][lb];
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> (str[i] + 1);

    while (m--) {
        char s[N];
        int limit;
        cin >> (s + 1) >> limit;
        int res = 0;
        for (int i = 0; i < n; i++)
            if (edit_distance(str[i], s) <= limit) res++;

        cout << res;
    }
    return 0;
}

区间DP

282 石子合并

282. 石子合并 - AcWing题库

  • 状态表示 \(f(i,j)\)\(i\) 堆到第 \(j\) 堆的区间
    • 集合
      • 将第 i 堆石子到第 j 堆石子合并成一堆石子的所有合并方式
    • 属性
      • \(min\) (每种合并方式的总代价 )
  • 状态计算
    • 以最后一次合并的分界线来分类(两堆合成一堆的分界线)
    • 左堆个数,右堆个数:1,k-1 | 2,k-2 | ... | k-1,1
    • 设分界线为k,先不考虑最后合并步骤,然后再加上最后合并的代价
    • 此时分为两堆 \([i,k],[k+1,j]\)
    • \(f(i,j)=Min(f(i,k)+f(k+1,j)+s[j]-s[i-1])\) ,后部分是前缀和求区间和
      • 左堆合并最小代价+右堆合并最小代价+最后合并的代价
      • \(k\in[i,j-1]\)

状态数量 \(n^2\) ,状态转移计算 n 次,时间复杂度 \(O(n^3)\)按区间长度从小到大枚举,从2到n

#include <algorithm>
#include <iostream>

using namespace std;

int const N = 3e2 + 10;
int n;
int s[N];
int f[N][N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> s[i];
    for (int i = 1; i <= n; i++) s[i] += s[i - 1];

    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int l = i, r = i + len - 1;
            f[l][r] = 1e9;  // 求min,初始化,不然每次都是 0
            for (int k = l; k < r; k++)
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }
    }
    cout << f[1][n];
    return 0;
}

计数DP

900⭐整数划分

900. 整数划分 - AcWing题库

通用解法

  • 状态表示 \(f(i,j)\)
    • 集合
      • 考虑前 \(i\) 个物品,物品总体积恰好为 j 的所有方案。完全背包
    • 属性
      • \(count\)
  • 状态计算
    • 不选第 i 个:\(f(i-1,j)\)
    • 选 i 的 k 个:\(f(i-1,j-V_i*k)\),优化为 \(f(i,j-V_i)\)
    • 转移方程:\(f(i,j) = f(i-1,j) + f(i,j-V_i)\)

#include <algorithm>
#include <iostream>

using namespace std;

int const N = 1e3 + 10;

int n;
int v[N];
unsigned f[N];

int main() {
    cin >> n;
    f[0] = 1;
    unsigned mod = (1e9 + 7);
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            f[j] = (f[j] + f[j - i]) % mod;
        }
    }
    cout << f[n];
    return 0;
}

另类解法

  • 状态表示 \(f(i,j)\)
    • 集合
      • 总和是 \(i\) ,并且恰好表示成 \(j\) 个数的和的所有方案
    • 属性
      • \(count\)
  • 状态计算
    • j 个数里最小值是 1
      • \(f(i-1,j-1)\)
    • j 个数里最小值大于 1
      • 把每一个数都减去一个1
      • \(f(i-j,j)\)
    • \(f(i,j) = f(i-1,j-1) +f(i-j,j)\)
#include <algorithm>
#include <iostream>

using namespace std;
unsigned mod = (1e9 + 7);
int const N = 1e3 + 10;
int n;
int f[N][N];

int main() {
    cin >> n;
    f[0][0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res = (res + f[n][i]) % mod;
    }
    cout << res;

    return 0;
}

状态压缩DP

用一个 \(n\) 位二进制数,每一位表示一个物品,0/1 表示不同的状态。因此可以用 \([0,2^n − 1]\) 中的所有数来枚举全部状态

291 蒙德里安的梦想

291. 蒙德里安的梦想 - AcWing题库

摆放长方形的时候,先放横着的,再放竖着的,确保能放满。总方案数等于只放横着小方块的合法方案数

  • 状态表示 \(f(i,j)\)
    • 集合
      • 已将前 i -1 列摆好,且从第 i − 1 列伸出到第 i 列的状态是 j 的所有方案
      • 状态 j 是二进制串,当前列每个格子的状态如 101001(1代表前一列该行放了长方形)
    • 属性
      • \(count\)
  • 状态计算
    • 第 i - 1 列状态 k ,第 i 列状态 j
    • 转移方程 \(f(i,j) = \sum f(i-1,k)\)
    • j 与 k 需满足
      • 没有重行 (j & k) == 0
      • k 与 j 并集后的状态连续 0 数量不是奇数 st[j | k]

  • 预处理j | k所有可能的状态,也就是 \([1,2^n)\),判断每个状态是否出现了奇数个连续0,若出现 st[i] 设置为false
  • f[0][0] = 1 根据状态表示,-1 层并不存在,横着摆放长方形个数为 0,那么只有竖着摆放一个方案
  • f[m][0] 是最终结果,此时摆放好了 \([0,m-1]\) 层,总共 m 层,第 m 层不能横着放长方形,因此 j 为 0
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 12, M = 1 << N;
int n, m;
long long f[N][M];
bool st[M];

int main() {
    int n, m;
    while (cin >> n >> m, n || m) {
        memset(f, 0, sizeof f);
        // 预处理,列举所有状态,连续0为奇数的状态置为True
        for (int i = 0; i < (1 << n); i++) {
            st[i] = true;
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                if (i >> j & 1) {
                    if (cnt & 1) {
                        st[i] = false;
                        break;
                    }
                    cnt = 0;
                } else
                    cnt++;
            }
            if (cnt & 1) st[i] = false;
        }
        // DP
        f[0][0] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < 1 << n; j++) {
                for (int k = 0; k < 1 << n; k++) {
                    if ((j & k) == 0 && st[j | k]) f[i][j] += f[i - 1][k];
                }
            }
        }
        cout << f[m][0] << endl;
    }
    return 0;
}

91 最短Hamilton路径

91. 最短Hamilton路径 - AcWing题库

朴素做法时间复杂度 \(O(n!*n)\):最坏情况下全排列,然后每个排列算一遍长度,肯定TLE

  • 状态表示 \(f(i,j)\)
    • 集合
      • 所有从 \(0\) 点走到 \(j\) 点,走过的所有点是 \(i\) 的所有路径
      • \(i\) 是二进制数,每一位表示当前点是不是走过
    • 属性
      • \(min\) (每个路径的长度)
  • 状态计算
    • 枚举倒数第二个点是哪个点 \(k\in[0,n-1]\)
    • \(f(i-\{ j \},k)\) 所有从 0 走到 k 且不经过 j 的点的所有路径的最短距离
    • 转移方程 \(f(i,j) = min(f(i-\{ j \},k) + a(k,j))\)

  • 从 0 开始走,0 点在二进制1号位,所以 f[1][0] = 0
#include <bits/stdc++.h>

using namespace std;

const int N = 20, M = 1 << 20;

int n;
int w[N][N];
int f[M][N];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) cin >> w[i][j];
    }
	// 求min,初始化
    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    for (int i = 0; i < 1 << n; i++) {
        for (int j = 0; j < n; j++) {
            // i 是否记录已走过 j 点
            if (i >> j & 1)
                for (int k = 0; k < n; k++) {
                    // i 记录了 k 点
                    if (i >> k & 1)
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
                }
        }
    }

    cout << f[(1 << n) - 1][n - 1] << endl;

    return 0;
}

树形DP⭐

285 没有上司的舞会

AcWing 285. 没有上司的舞会 - AcWing

  • 状态表示 \(f(u,0)\) \(f(u,1)\)
    • 集合
      • \(f(u,0)\) 以 u 为根的子树中选择,并且不选 u 这个点的所有方案
      • \(f(u,1)\) 以 u 为根的子树中选择,并且选 u 这个点的所有方案
    • 属性
      • \(max\) (每个方案的快乐指数)
  • 状态计算 (\(si\) 为 u 的所有儿子)
    • \(f(u,0) = \sum Max(f(si,0),f(si,1))\)
    • \(f(u,1) = \sum f(si,0)\)

所有节点总儿子数量等于边数 n - 1 ,整个问题时间复杂度 \(O(n)\)


#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

int const N = 6e3 + 10;

int n;
int happy[N];
int h[N], e[N], ne[N], idx;
int f[N][2];
bool has_father[N];

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dfs(int u) {
    f[u][1] = happy[u];

    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        dfs(j);
        f[u][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0];
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> happy[i];
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        has_father[a] = true;
        add(b, a);
    }
    int root = 1;
    while (has_father[root]) root++;

    dfs(root);

    cout << (max(f[root][0], f[root][1])) << endl;
    return 0;
}

记忆化搜索

每一道动态规划问题都可以用递归方式来写(如上面的树形DP)

901 滑雪

901. 滑雪 - AcWing题库

  • 状态表示 \(f(i,j)\)
    • 集合
      • \(i,j\) 开始滑的所有路径
    • 属性
      • \(max\) (每个路径的长度)
  • 状态计算
    • 按第一步往哪个方向滑分为四类(即先不考虑第一步,再考虑第一步)
    • 往右划: \(f(i,j+1) + 1\) ,其他同理(要考虑存在条件,滑到点高度小于当前点)

同时递归不应该存在环。题目能满足要求(点与点的高度差关系)

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

int const N = 3e2 + 10;

int n, m;
int h[N][N];
int f[N][N];

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int dp(int x, int y) {
    int &v = f[x][y];
    if (v != -1) return v;
    v = 1;  // 不能走,路径为1
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && h[nx][ny] < h[x][y]) {
            v = max(v, dp(nx, ny) + 1);
        }
    }
    return v;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> h[i][j];

    memset(f, -1, sizeof f);
    int res = 0;
    // 遍历每一个起点的最大值
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) res = max(res, dp(i, j));
    cout << res;
    return 0;
}

参考资料

感谢所有大佬的题解,所有博客知识分享。ORZ

OI Wiki - OI Wiki (oi-wiki.org)

多重背包问题 III【单调队列优化+图示】

AcWing 11. 背包问题求方案数【背包DP求最优方案总数】

背包问题中 体积至多是 j ,恰好是 j ,至少是 j 的初始化问题的研究

AcWing 1013. 机器分配【分组背包+背包DP输出方案—拓扑图分析】 - AcWing

AcWing 291. 蒙德里安的梦想 - AcWing

AcWing 291. 蒙德里安的梦想(详细注释 ) - AcWing

AcWing 91. 最短Hamilton路径(超详解) - AcWing

AcWing 12. 背包问题求具体方案【01背包 + 背包DP输出方案】 - AcWing

热门相关:落地一把98K   慕少,你老婆又重生了   嫡嫁千金   悠哉兽世:种种田,生生崽   名门盛婚:首席,别来无恙!