区间dp--石子合并

题目表示

有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。
举例1：
2，4，5
总代价最小值为17
举例2：
4，1，1，4
总代价最小值为18

题目解析

这是一个经典的区间DP问题，也被称为“石子合并”或“石子游戏”。

我们可以这样定义状态和方程：

定义 dp[i][j] 为合并从第 i 堆到第 j 堆石子的最小代价。

因为合并的代价是两堆石子的和，所以我们还需要一个前缀和数组 prefix，其中 prefix[k] 代表第1堆到第k堆的石子数量总和。

状态转移方程为：
[ dp[i][j] = \min_{i \leq k < j}(dp[i][k] + dp[k+1][j] + prefix[j] - prefix[i-1]) ]
其中，( prefix[j] - prefix[i-1] ) 是第i堆到第j堆的石子总和。

初始条件：当 i == j 时，dp[i][j] = 0，因为只有一堆石子不需要合并。

算法流程如下：

1. 初始化 dp 为0，并计算前缀和数组 prefix。
2. 从小到大遍历区间长度 len，从2到N。
3. 对于每一个长度 len，从头开始遍历起始点 i，计算结束点 j = i + len - 1。
4. 对于每一对 (i, j)，遍历所有可能的分割点 k，更新 dp[i][j]。

#include 
#include 
#include 
#include 

using namespace std;

int stoneMerging(vector<int>& stones) {
   
    int N = stones.size();
    vector<vector<int>> dp(N+1, vector<int>(N+1, 0));
    vector
1
2
3
4
5
6
7
8
9
10
11