区间DP
定义
区间 DP 是动态规划的一种特殊形式，主要是在一段区间上进行动态规划计算。
运用情况
通常用于解决涉及在一段区间内进行操作、计算最优值等问题。比如计算一个区间内的最大子段和、最小分割代价等。一些常见的场景包括合并操作、划分操作等在区间上进行的任务。
注意事项
- 要正确定义状态，通常状态会包含区间的起始点和结束点等信息。
- 仔细考虑状态转移方程，确保涵盖所有可能的情况。
- 注意边界条件的处理。
解题思路
- 明确问题是可以转化为区间上的计算。
- 设计合适的状态表示，例如用 dp[i][j] 表示区间 [i, j] 上的某种最优值。
- 找出状态转移方程，即如何从较小的区间的最优值推导出较大区间的最优值。
- 按照合适的顺序进行计算，通常是从小到大逐步计算出各个区间的最优值。
例如，对于计算一个区间的最大连续子段和问题，我们可以定义 dp[i][j] 为区间 [i, j] 的最大子段和，状态转移方程可能是 dp[i][j] = max(dp[i][j-1] + nums[j], nums[j])。然后通过两层循环遍历所有可能的区间来计算出最终结果。
AcWing 282. 石子合并
题目描述
AcWing 282. 石子合并 - AcWing
运行代码
#include <iostream>
#include <cstring>
#include <climits>
using namespace std;
const int N = 305;
int dp[N][N];
int sum[N];
int stones[N];
int minCost(int l, int r) {
if (dp[l][r]!= -1) {
return dp[l][r];
}
if (l == r) {
return 0;
}
int minVal = INT_MAX;
for (int k = l; k < r; k++) {
int cost = minCost(l, k) + minCost(k + 1, r) + sum[r] - sum[l - 1];
minVal = min(minVal, cost);
}
dp[l][r] = minVal;
return minVal;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> stones[i];
sum[i] = sum[i - 1] + stones[i];
}
memset(dp, -1, sizeof(dp));
cout << minCost(1, n) << endl;
return 0;
}代码思路
-
const int N = 305;：定义了一个常量表示最多可能的石子堆数。 -
int dp[N][N];：这是用于存储区间[l,r]的最小合并代价的二维数组。 -
int sum[N];：用于计算前缀和，方便后续计算区间的石子质量总和。 -
int stones[N];：存储每堆石子的质量。 -
minCost函数是核心函数，它通过递归和动态规划来计算区间[l,r]的最小代价：- 如果
dp[l][r]已经计算过（不为-1），则直接返回该值，避免重复计算。 - 当区间只有一堆石子（
l == r）时，代价为 0。 - 然后通过遍历区间内的分割点
k，计算将区间分为两部分合并的代价，取其中的最小值。最后将计算得到的最小代价存储到dp[l][r]中。
- 如果
-
在
main函数中：- 输入石子堆数
n和每堆石子的质量。 - 计算前缀和。
- 将
dp数组初始化为-1。 - 调用
minCost(1,n)计算并输出最终的最小代价。
- 输入石子堆数
改进思路
- 空间优化：可以观察到在计算过程中，实际上只需要用到当前正在计算的较小区间的 dp 值，可以考虑滚动数组等方式来减少空间复杂度。
- 预处理一些信息：比如提前计算好一些常见区间的和，避免在计算代价时重复计算。
- 并行计算：如果有合适的硬件环境，可以考虑对一些不相互依赖的计算部分进行并行化处理，提高计算效率。
- 更高效的状态转移：进一步分析问题特性，看是否能找到更简洁或更高效的状态转移方式。
- 添加错误处理：增加对输入数据的合法性检查等错误处理机制，使程序更加健壮。
其它代码
#include <iostream>
#define N 310
#define inf 0x3f3f3f3f
using namespace std;
int n;
int f[N][N], s[N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++ ) cin >> s[i], s[i] += s[i - 1];
for(int len = 2; len <= n; len ++ )
for(int l = 1; l + len - 1 <= n; l ++ )
{
int r = l + len - 1;
f[l][r] = inf;
for(int k = l; k < r; k ++ )
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] - s[l - 1] + s[r]);
}
cout << f[1][n] << endl;
return 0;
}代码思路
#define N 310和#define inf 0x3f3f3f3f：定义了常量表示最大可能的元素数量和一个较大的数值表示无穷大。int n：表示元素的个数。int f[N][N]：这个二维数组用于存储区间[l,r]的最小代价。int s[N]：用于计算前缀和。
在 main 函数中：
- 首先输入元素个数
n，并计算前缀和s。 - 然后通过两个嵌套的循环来处理不同长度的区间：对于每个长度的区间，通过遍历可能的分割点
k，计算将区间分为两部分的代价，取最小值更新f[l][r]。这里的代价计算是基于当前区间的分割代价以及前缀和来确定的。 - 最后输出区间
[1,n]的最小代价，即f[1][n]。
