动态规划——石子合并问题

问题描述

审题

如图，红框起位置告知了为圆形操场，即石子需要环形排列

且需要相邻的石子堆才能合并，每次合并的得分是两个堆的石子数量之和。最终，我们需要把所有石子合并成一堆，并且需要计算出最小得分和最大得分。

思考

在合并过程中，得分依赖于合并的顺序。举个十分简单的例子：
例如，如果我们有三堆石子 [4, 4, 5]，不同的合并顺序会导致不同的得分，总共有两种合并顺序，分别为21和22。

这类问题存在大量重叠子问题，即子问题的解可以被多次重复利用，而这些子问题的结果依赖于更小的子问题结果。这正是动态规划的特点，所以我们可以采用动态规划的思想来求解。

动态规划思想

参考：
看一遍就理解：动态规划详解
动态规划-斐波那契数列

动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。

最优子结构：问题的最优解可以通过子问题的最优解来构建。这意味着我们可以递归地解决问题，同时利用之前的计算结果。

重叠子问题：许多子问题会在递归过程中被多次遇到。通过存储这些子问题的解，我们避免了冗余的计算。

看到这里，是不是还挺容易联想到经典的斐波那契数列，对的没错

动态规划类似分治，同样是将原问题分解成子问题，通过求解子问题而得到原问题的解。但不同的是，动态规划是自底向上分解，并且会保存子问题的解，在需要时可直接拿过来使用，这一点是区别于分治的。通过对子问题解的保存，可以避免大量重复计算，从而提高运行效率。例如上述斐波那契数列，由数学公式得到：当n>1时，第n项是前两项结果的和。如下图所示：

如计算F（5）的时候，会多次用到F（1）和F（2）的结构结果，那么使用动态规划思想可在之前的过程中存储这些子问题的解
这样在接下来自底向上的过程中能够不断使用子问题的解的和来获取最后问题的解

应用

1.题目提到了圆形操场，并非是普通的线性排列，还需要考虑首尾相邻的情况

此时可以通过扩展数组来模拟环形结构，应用复制数组的方法。

也就是从[4,4,5,9]到[4,4,5,9,4,4,5,9]

2.动态规划中的状态转移

核心代码

---

逐层解释：

1. 外层循环 (length)：

   for (int length = 2; length <= n; length++)
   

   • 作用： 控制当前处理的区间长度，从 2 增加到 n。
   • 目的： 按照区间长度从小到大进行动态规划计算，确保在计算较长区间时，所需的较短区间的结果已经被计算并存储。

2. 中间循环 (i)：

   for (int i = 0; i <= 2 * n - length; i++)
   

   • 作用： 控制区间的起始位置 i。

   • j 的计算：

     int j = i + length - 1;
     

     • j 是区间的结束位置，根据 i 和 length 计算得出。
     • 区间 [i, j] 的长度为 length。

   • 目的： 枚举所有长度为 length 的区间 [i, j]。

3. 内层循环 (k)：

   for (int k = i; k < j; k++)
   

   • 作用： 控制区间 [i, j] 内的划分点 k。
   • 目的： 尝试将区间 [i, j] 划分为两个更小的子区间 [i, k] 和 [k+1, j]，以便利用已计算的子区间结果来更新当前区间的最优解。

---

• 外层循环 length：控制了区间的长度，从 2 到 n。

• 中间循环 i 和 j：

  • i： 控制当前区间的起始位置。
  • j： 通过 j = i + length - 1 计算得到，控制当前区间的结束位置。
  • 因此，i 和 j 确定了当前正在处理的区间 [i, j]，它的长度就是 length。

• 内层循环 k：

  • k： 控制划分点，将区间 [i, j] 划分为两个更小的子区间。
  • 目的： 通过尝试不同的划分方式，找到合并区间 [i, j] 的最小和最大得分。

所以，正确的理解是：

• 外层循环 length： 控制当前处理的区间长度，从小到大递增。

• 中间循环 i 和计算得到的 j： 确定当前区间的起始和结束位置 [i, j]，该区间的长度为 length。

• 内层循环 k： 在当前区间 [i, j] 内，尝试所有可能的划分点，以找到最优的合并方式。

---

举个例子帮助理解：

假设 n = 4，石子堆数为 [4, 5, 3, 2]，扩展后为 [4, 5, 3, 2, 4, 5, 3, 2]。

1. 当 length = 2 时：

   • 区间长度为 2。
   • i 的取值范围： 从 0 到 2 * n - length = 6，即 i = 0 到 6。
   • 对应的区间 [i, j]： [0,1], [1,2], [2,3], [3,4], [4,5], [5,6], [6,7]。
   • 在每个区间内：
     • 划分点 k 只有一个，即 k = i。
     • 计算并更新 dp_min[i][j] 和 dp_max[i][j]。

2. 当 length = 3 时：

   • 区间长度为 3。
   • i 的取值范围： 从 0 到 5。
   • 对应的区间 [i, j]： [0,2], [1,3], [2,4], [3,5], [4,6], [5,7]。
   • 在每个区间内：
     • 划分点 k 有两个：k = i 和 k = i + 1。
     • 尝试不同的划分方式，更新 dp_min[i][j] 和 dp_max[i][j]。

---

总结：

• 外层循环 length： 控制了区间的长度，从 2 到 n。

• 中间循环 i 和 j： 确定了当前处理的区间 [i, j]，长度为 length。

• 内层循环 k： 在区间 [i, j] 内尝试所有可能的划分点，寻找最优解。

因此，i 和 j 并不是控制“小区间的长度”，而是确定了当前区间的起点和终点。小区间（子区间）的长度和位置是通过划分点 k 来确定的。

代码

#include <stdio.h>
#include <limits.h>  // 用于 INT_MAX#define MAXN 200// 前缀和数组
int prefix_sum[MAXN + 1];// dp_min[i][j] 表示从第 i 堆石子到第 j 堆石子合并成一堆的最小得分
int dp_min[MAXN][MAXN];// dp_max[i][j] 表示从第 i 堆石子到第 j 堆石子合并成一堆的最大得分
int dp_max[MAXN][MAXN];// 计算从第 i 堆到第 j 堆石子的总和
int get_sum(int i, int j) {return prefix_sum[j + 1] - prefix_sum[i];
}int main() {int n;int stones[MAXN];// 输入堆数scanf("%d", &n);// 输入每堆的石子数for (int i = 0; i < n; i++) {scanf("%d", &stones[i]);stones[i + n] = stones[i];  // 模拟环形，将石子数组扩展一倍}// 计算前缀和prefix_sum[0] = 0;for (int i = 1; i <= 2 * n; i++) {prefix_sum[i] = prefix_sum[i - 1] + stones[i - 1];}// 初始化 dp 数组for (int i = 0; i < 2 * n; i++) {for (int j = 0; j < 2 * n; j++) {dp_min[i][j] = (i == j) ? 0 : INT_MAX;dp_max[i][j] = 0;}}// 动态规划计算 dp_min 和 dp_maxfor (int length = 2; length <= n; length++) {  // length 表示区间长度for (int i = 0; i <= 2 * n - length; i++) {int j = i + length - 1;for (int k = i; k < j; k++) {dp_min[i][j] = (dp_min[i][j] < dp_min[i][k] + dp_min[k + 1][j] + get_sum(i, j)) ? dp_min[i][j] : dp_min[i][k] + dp_min[k + 1][j] + get_sum(i, j);dp_max[i][j] = (dp_max[i][j] > dp_max[i][k] + dp_max[k + 1][j] + get_sum(i, j)) ? dp_max[i][j] : dp_max[i][k] + dp_max[k + 1][j] + get_sum(i, j);}}}// 计算最小得分和最大得分int min_score = INT_MAX;int max_score = 0;for (int i = 0; i < n; i++) {min_score = (min_score < dp_min[i][i + n - 1]) ? min_score : dp_min[i][i + n - 1];max_score = (max_score > dp_max[i][i + n - 1]) ? max_score : dp_max[i][i + n - 1];}// 输出结果printf("%d\n", min_score);  // 输出最小得分printf("%d\n", max_score);  // 输出最大得分return 0;
}

3. 动态规划需要考虑所有可能的合并方式

子问题划分： 为了找到最优的合并顺序，我们需要考虑如何将区间 [i, j] 划分为更小的子区间 [i, k] 和 [k+1, j]，并递归地计算它们的最优解。

状态转移：

当前区间的最优解可以由其子区间的最优解和合并代价构成。

公式：dp_min[i][k] + dp_min[k + 1][j] + get_sum(i, j)
​

解释：

dp_min[i][j]： 合并区间 [i, j] 的最小得分。
dp_min[i][k] 和 dp_min[k+1][j]： 左右子区间的最小得分。
get_sum(i, j)： 合并整个区间 [i, j] 的代价（即石子总数）。
通过尝试不同的划分点 k，我们可以找到使 dp_min[i][j] 最小的合并方式。