Hz的DP总结

前言：

鉴于本人是一个DP低手，以后每写一道DP都会在本篇博客下进行更新，包括解题思路，方法，尽量做到分类明确，其中的题目来自包括但并不限于牛客，洛谷，CodeForces，AtCoder等平台，希望有朝一日也能独立写出2000分的DP。

正片：

线性DP：

Educational Codeforces Round 174 (Rated for Div. 2) C. Beautiful Sequence

这道题真是赛时不知道怎么推，赛后一看题解就觉得自己是个XX。

• 知识点：思维，递推

简单来讲就是要求一下形如 1 2 2 2 … 2 3 这样的子序列的个数。

考虑线性递推：f[i][1, 2, 3] 表示以第i个数字结尾的，且a[i] = 1, 2, 3 的满足条件的序列数；
这里对状态方程的定义有点模糊，因为这里严格来讲不太像DP，更像是一种递推。

看一下转移，首先借助前缀和的思想，f[i] = f[i - 1]，三个状态的数量都等于上一步的数量，再加上这一步的贡献。

• 对于a[i] == 1;
  f[i][1] += 1;
• 对于a[i] == 2;
  f[i][2] += f[i - 1][2];
  // 可以看作这个2可以加在之前任何一个以2结尾的序列的末尾，所以就是加上之前所有的。
  f[i][2] += f[i - 1][1];
  // 也可以是直接接在之前任何一个1的末尾，所以加上1的数量。
• 对于a[i] == 3;
  f[i][3] += f[i][2];
  就是答案。

#include<bits/stdc++.h>using namespace std;
using i64 = long long;
using u64 = unsigned long long;#define int long long
#define debug(x) cerr << #x" = " << x << '\n';typedef pair<int, int> PII;const i64 N = 2e5 + 10, INF = 1e18 + 10;int mod = 998244353;void solve()
{int n;cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i++) {cin >> a[i];}vector<int> f(4, 0);for (int i = 1; i <= n; i++) {if (a[i] == 1) {(f[1] += 1) %= mod;} else if (a[i] == 2) {(f[2] += f[2]) %= mod;(f[2] += f[1]) %= mod;} else if (a[i] == 3) {(f[3] += f[2]) %= mod;}}cout << f[3] % mod << endl;
}signed main()
{cin.tie(0) -> ios::sync_with_stdio(false);int T = 1;cin >> T;while (T --) solve();return 0;
}

这里其实不难发现每一次f 都是由 i - 1转移过来，所以可以直接省去一维。

背包DP：

牛客周赛 Round 81 E.建筑入门

• 知识点：完全背包，完全背包的路径转移以及回溯

由题意可以推导出，下层麻将的数字一定大于上层数字，所以我们可以假设一个最基础的麻将塔，也就是：
1
2 2
3 3 3
…
形如这样的，然后再从下往上一层一层加数字，且得保证下层一定得大于上层，所以可以想象成，如果倒数第二层加数字的话，倒数第一层也得加数字，那就可以翻译成 选择一个从第i层向下的后缀层数，每一层每一个块均+1，然后选择若干这样的后缀和，最后使得总值正好等于k。

这也就是转化成了一个经典的完全背包问题。
f[i][j] 表示 前i个数字里面选择之后数字和恰好为j能否做到，记录的是一个bool类型的值

但是还有个问题：如何记录路径？
学过01背包的小伙伴肯定都知道01背包记录路径的方法，只需要记录选择了哪件物品即可，但是介于完全背包每个物品可以选择很多件，所以不能单单记录选择了哪件物品，这就需要记录我们的背包体积是什么时候发生变化的。

vector<PII> path(k + 1);  // 记录一下当前体积为 i 的上一步体积是多少

一些回溯包括其他的细节大家参考代码理解吧

#include<bits/stdc++.h>using namespace std;
using i64 = long long;
using u64 = unsigned long long;#define int long long
#define debug(x) cerr << #x" = " << x << '\n';typedef pair<int, int> PII;const i64 N = 2e5 + 10, INF = 1e18 + 10;void solve()
{int n, k;cin >> n >> k;k = k - n * (n + 1) * (2 * n + 1) / 6;  // 1^1 + 2^2 + 3^3 + ... + n^nif (k < 0) {cout << -1 << endl;return;}vector<int> a(n + 2);for (int i = n; i > 0; i--) {a[i] = a[i + 1] + i;}vector<vector<int>> f(n + 1, vector<int>(k + 1, 0));  // 前i个数字里面选择之后数字和恰好为j能否做到vector<PII> path(k + 1);  // 记录一下当前体积为 i 的上一步体积是多少f[0][0] = 1;for (int i = 1; i <= n; i++) {  // （以倒数第n行为开始的后缀）（倒数第n - 1行开始的）。。for (int j = 0; j <= k; j++) {f[i][j] = f[i - 1][j];if (j - a[i] >= 0 && f[i][j - a[i]]) {f[i][j] = 1;path[j] = {j - a[i], i};// 体积为 j 的上一步是 j - a[i];// 把第i号物品拿过来之后进行的转移}}}if (!f[n][k]) {cout << -1 << endl;return;}vector<int> nums;int curr = k;while(curr > 0) {auto [pre, x] = path[curr];nums.emplace_back(x);curr = pre;}vector<int> ans(n + 1, 0);for (auto &x : nums) {ans[x]++;}for (int i = 1; i <= n; i++) {ans[i] += ans[i - 1];}for (int i = 1; i <= n; i++) {ans[i] += i;cout << ans[i] << " \n"[i == n];}
}signed main()
{cin.tie(nullptr) -> ios::sync_with_stdio(false);int T = 1;// cin >> T;while (T --) solve();return 0;
}

和数据结构结合的DP：

单调栈：Codeforces Round 622 (Div. 2) C2. Skyscrapers (hard version)

简单来讲就是最后需要呈现出一个单峰数组，使得总高度最高。

最开始想到暴力枚举每一个元素都充当最高的“单峰”，但是这里的 n 过大，这样枚举肯定会TLE。

那就考虑能不能单调线性的考虑每个元素作为最高点的时候的解是多少呢？

这里就需要借助我们的 单调栈，维护一个单调递增的序列：

• 这里仅以正序遍历为例：f[i]表示的是以i为单峰时1 — i 所有数组能产生的最大贡献，根据单调栈的性质，stk.top()就是上一个最近的小于 a[i] 的元素的下标，所以加上这中间所有的楼产生的贡献（由于单调栈的性质，这段中所有大于a[i] 的元素一定会被弹出，同时减去他们之前产生的贡献）。

#include<bits/stdc++.h>using namespace std;#define int long longsigned main() {int n, sum = 0;cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i++) {cin >> a[i];}stack<int> stk;vector<int> f(n + 1, 0);sum = 0;for (int i = 1; i <= n; i++) {while(stk.size() && a[stk.top()] >= a[i]) {//先弹出所有大于a[i]的楼的下标，因为保证要单增int j = stk.top();stk.pop();sum -= (j - (stk.empty() ? 0 : stk.top())) * a[j];// 减去这些楼之前所产生的贡献}sum += (i - (stk.empty() ? 0 : stk.top())) * a[i]; //加上目前这栋楼所产生的贡献stk.push(i);f[i] += sum;}sum = 0;while(!stk.empty()) stk.pop(); for (int i = n; i >= 1; i--) {while(stk.size() && a[stk.top()] >= a[i]) {int j = stk.top();stk.pop();sum -= ((stk.empty() ? n + 1 : stk.top()) - j) * a[j];}sum += ((stk.empty() ? n + 1 : stk.top()) - i) * a[i];stk.push(i);f[i] += sum - a[i];}auto p = max_element(f.begin() + 1, f.end()) - f.begin();//cout << p << endl;for (int i = p - 1; i >= 1; i--) {a[i] = min(a[i], a[i + 1]);}for (int i = p + 1; i <= n; i++) {a[i] = min(a[i], a[i - 1]);}for (int i = 1; i <= n; i++) {cout << a[i] << " \n"[i == n];}return 0;
}

建议先熟练掌握单调栈再来理解这题。

概率DP：