动态规划：区间DP(石子合并) 、 计数类DP(整数划分)

区间DP

AcWing 282. 石子合并

设有 \(N\) 堆石子排成一排，其编号为 \(1，2，3，…，N\)。

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 \(N\) 堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

例如有 \(4\) 堆石子分别为 1 3 5 2， 我们可以先合并 \(1、2\) 堆，代价为 \(4\)，得到 4 5 2， 又合并 \(1，2\) 堆，代价为 \(9\)，得到 9 2 ，再合并得到 \(11\)，总代价为 \(4+9+11=24\)；

如果第二步是先合并 \(2，3\) 堆，则代价为 \(7\)，得到 4 7，最后一次合并代价为 \(11\)，总代价为 \(4+7+11=22\)。

问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

输入格式

第一行一个数 \(N\) 表示石子的堆数 \(N\)。

第二行 \(N\) 个数，表示每堆石子的质量(均不超过 \(1000\))。

输出格式

输出一个整数，表示最小代价。

数据范围

\(1≤N≤300\)

输入样例：

4
1 3 5 2

输出样例：

22

code:

#pragma once
#include 

using namespace std;

const int N = 1010;

int f[N][N], n, prefix_sum[N];//f表示状态，n表示个数，prefix_sum表示前缀和
// f[i][j] 表示所有将第i堆石子到第j堆石子合并成一堆石子的方式的集合, 属性值是集合的最小值

void combine_rock_piles()
{
	// 处理输入
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> prefix_sum[i];

	// 处理前缀和
	for (int i = 1; i <= n; ++i) prefix_sum[i] += prefix_sum[i - 1];

	// 按照长度从小到大枚举状态
	for (int len = 2; len <= n; ++len) // 直接从区间为2开始枚举，因为1不需要合并，代价为0，而f[i][i]默认就是零
		//枚举起点
		for (int i = 1; i + len - 1 <= n; ++i)
		{
			int l = i, r = i + len - 1; //初始化区间左右端点值，枚举区间，这里的区间都是大于1的，区间为1的默认为0
			f[l][r] = 1e8; //算f[i][j]之前初始化成正无穷, 要不然就全部是零了
			for (int k = l; k < r; ++k)
				f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + prefix_sum[r] - prefix_sum[l - 1]);
		}

	cout << f[1][n] << endl;
}

计数类DP

AcWing 900. 整数划分

一个正整数 \(n\) 可以表示成若干个正整数之和，
形如：\(n=n_1+n_2+…+n_k，其中n_1≥n_2≥…≥n_k,k≥1\)。
我们将这样的一种表示称为正整数 \(n\) 的一种划分。 现在给定一个正整数 \(n\)，请你求出\(n\)共有多少种不同的划分方法。

输入格式
共一行，包含一个整数 \(n\)。

输出格式
共一行，包含一个整数，表示总划分数量。 由于答案可能很大，输出结果请对 \(10^9+7\) 取模。

数据范围
1≤n≤1000

输入样例:

5

输出样例：

7

解法一：
转化为完全背包问题求解, \(f[i][j]\) 表示从 \(1~i\) 中选总体积恰好为 \(j\) 的选法数量。
状态计算：
\(f[i][j] = f[i - 1[j]+f[i - 1][j - 1]+f[i - 1][j - 2]+……+f[i - 1][j - i * s]\)
\(f[i][j - i] = \ \ \ \ \ \ \ \ \ \ \ \ \ \ f[i - 1][j - 1]+f[i - 1][j - 2]+……+f[i - 1][j - i * s](s为 i * s ≤ j 下的最大值）\)
因此，\(f[i][j] = f[i - 1][j] + f[i][j - i]\)

#pragma once
#include 

using namespace std;
const int N = 1010, mod = 1e9 + 7;

int f[N];
// f[i][j]表示从1 ~ i物品中所有选取体积恰好为j得选法得集合
// 集合属性值是所有得方案数加在一起
// f[i][j] = f[i - 1][j] + f[i][j - i]
void integer_division()
{
	int n;
	cin >> n;
	f[0] = 1; //出了f[0]之外都是0, 这是初始化
	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] << endl;
}

解法二：
\(f[i][j]\) 表示所有总和是 \(i\)，并且恰好表示成 \(j\) 个数的和的方案数。
状态计算：
划分为最小值为 \(1\) 时，方案数为 \(f[i - 1][j - 1]\)；最小值大于 \(1\) 时，方案数为 \(f[i - j][j]\).
则 \(f[i][j] = f[i -1][j - 1] + f[i - j][j]\)，最终结果是 \(f[n][1]+f[n][2]+……+f[n][n]\).

#pragma once
#include 

using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N][N];
void integer_division2()
{
	int n;
	cin >> n;

	f[0][0] = 1; //总和是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 j = 1; j <= n; ++j) res = (res + f[n][j]) % mod;

	cout << res << endl;
}