Acwing 区间DP 计数类DP

1.区间DP

Acwing 282.石子合并
在这里插入图片描述
思路分析：

f(i,j)表示将第i堆石子到第j堆石子合并为一堆时的最小代价；
状态划分：选一个分割点k，将[i-k]和[k+1,j]这两个区间的石子合并，然后加上两个区间的合并总代价（采用前缀和计算区间i到j的值，s[j]-s[i-1]😉
初始从枚举区间长度开始（即石子堆数），区间长度len从2到n枚举（从2开始是因为，若len为1，则没必要合并）
然后枚举左端点i，从l到i+len-1;
k从左端点i开始枚举，比如k=i+1时，区间被分割为(i,i+1)，(i+2,i+len-1)，左边区间就一堆，右边区间len-1堆；
状态转移方程：f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1])

具体实现代码（详解版）：

#include <iostream>
#include <algorithm>using namespace std;const int N = 310; 
int n; 
int s[N]; // 用于存储石子堆的大小，以及后续的前缀和
int f[N][N]; // 动态规划数组，f[l][r] 表示合并从第 l 堆到第 r 堆石子的最小代价int main() {cin >> n; for (int i = 1; i <= n; i++) {cin >> s[i];}// 计算前缀和数组// s[i] 表示从第1堆石子到第i堆石子的总和，用于快速计算区间内石子总和for (int i = 1; i <= n; i++) {s[i] += s[i - 1];}// 枚举区间长度 len，从2开始，因为长度为1的区间不需要合并for (int len = 2; len <= n; len++) {// 枚举区间的左端点 i，右端点 r = i + len - 1for (int i = 1; i + len - 1 <= n; i++) {int l = i, r = i + len - 1; // l 是左端点，r 是右端点// 初始化 f[l][r] 为一个很大的值，确保后面计算的最小值能够替换它f[l][r] = 1e8;// 枚举分割点 k，将区间 [l, r] 分成 [l, k] 和 [k+1, r] 两部分for (int k = l; k < r; k++) {// 动态规划转移方程：// 合并 [l, k] 和 [k+1, r] 的代价加上合并整个区间的代价f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);}}}// 输出从第1堆到第n堆的最小合并代价，即 f[1][n]cout << f[1][n] << endl;return 0;
}

2.计数类DP

Acwing 900.整数划分
在这里插入图片描述
实现思路：本题求的是方案个数，而不要求方案顺序，即4=1+1+2 和4=1+2+1是一样的
（1）方案一：转化为完全背包问题。将n看成是背包容量，而1~n之间的数看成物品，且各个物品的数量是无限的，至此转化为完全背包问题
在这里插入图片描述

f(i,j)表示从前i个数字（物品）中选择，之和恰好是j（体积）的方案个数
以第i个数字选择了几次（物品i放了几个）做集合划分。若只选0个i，那么前i-1数的选择之和已经满足j，故为f[i-1][j]；若第i个数字选择了k次，那么前i-1个数的选择之和为j-k*v[i]，故f[i-1][j-v[i]]
类似完全背包问题的分析与优化：

f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2i] + .... + f[i - 1][j - k*i]

f[i][j - i] = f[i - 1][j - i] + f[i - 1][j - 2i] + .... + f[i - 1][j - k*i]

所以：

状态转移方程：f[i][j] = f[i - 1][j] + f[i][j - i]

优化至一维

f[j] = f[j] + f[j - i]表示和为j的方案数量

具体实现代码（详解版）：

#include <iostream>
#include <algorithm>using namespace std;const int N = 1010, mod = 1e9 + 7; 
int n; 
int f[N]; // 动态规划数组 f[j] 表示将整数 j 拆分为若干正整数之和的方案数int main() {cin >> n; f[0] = 1; // 初始化 f[0] = 1，因为将0拆分为零个数只有一种方案（空方案）// 遍历所有正整数 i，表示我们将 i 作为拆分的一部分for (int i = 1; i <= n; i++) {// 遍历所有从 i 到 n 的数 j，更新将 j 拆分的方案数for (int j = i; j <= n; j++) {//转移方程f[j] = (f[j] + f[j - i]) % mod;}}cout << f[n] << endl;return 0;
}

（2）方案二
在这里插入图片描述

用f[i][j]表示，所有总和是i，并且恰好表示成j个数之和的方案的数量。
集合划分，能够分为如下两类:
- 方案中最小值是1的所有方案，这时候去掉一个1，此时和变成了i - 1 ，个数变成了j - 1 ，即f[i - 1][j - 1];
- 方案中最小值大于1的所有方案，此时将j个数都减去1，此时和变成了i - j(j个数每个数都-1，共-j)，个数还是j，即f[i - j][j];
最终状态转移方程为：f[i][j] = f[i - 1][j-1] + f[i-j][j];
结果输出应为f[n][1] + f[n][2] + f[n][3] + … + f[n][n]

具体实现代码（详解版）：

#include <iostream>
#include <algorithm>using namespace std;const int N = 1010, mod = 1e9 + 7; 
int n; 
int f[N][N]; int main() {cin >> n; f[0][0] = 1;//和为0，表示的方案为1for(int i = 1; i <= n; i ++){for(int j = 1; j <= i ; j ++){//两种情况:1.最小值是1；2.最小值大于1.f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;}}int res = 0;//f[n][1]+f[n][2]+...+f[n][n]for(int i = 1; i <= n; i ++) res =(res + f[n][i]) % mod;cout << res << endl;return 0;
}