直线石子合并

在一条直线上有n堆石子,每堆有一定的数量,每次可以将两堆相邻的石子合并,合并后放在两堆的中间位置,合并的费用为两堆石子的总数,求把所有石子合并成一堆的最小花费。

解决这个问题,我们可以使用动态规划(DP)。这个问题是典型的区间DP问题。基本思路是这样的:

  1. 定义状态:dp[i][j]表示将第i堆到第j堆石子合并成一堆的最小花费。
  2. 状态转移方程:dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum[i][j]),其中i <= k < jsum[i][j]表示第i堆到第j堆石子的总数。
  3. 初始化:对于任何idp[i][i] = 0,因为单独一堆石子不需要合并。
  4. 计算顺序:从小区间到大区间,即先计算长度为2的区间,然后是长度为3的区间,依此类推。

代码实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**************************************************************** 
 * Description: 直线石子合并
 * Author: Alex Li
 * Date: 2024-02-22 16:56:01
 * LastEditTime: 2024-02-22 17:10:56
****************************************************************/
#include <iostream>
#include <vector>
#include <climits> // 用于INT_MAX

using namespace std;

int mergeStones(vector<int>& stones) {
    int n = stones.size();
    // 初始化dp数组
    vector<vector<int> > dp(n, vector<int>(n, 0));
    vector<int> prefixSum(n + 1, 0);
    //初始化前缀和数组
    for (int i = 0; i < n; ++i) {
        prefixSum[i + 1] = prefixSum[i] + stones[i];
    }
    
    // 计算所有可能的区间
    for (int len = 2; len <= n; ++len) { // 区间长度从2开始
        for (int i = 0; i <= n - len; ++i) {
            int j = i + len - 1; // 计算区间的右端点
            dp[i][j] = INT_MAX;  //初始化i-j区间的最小值是INT_MAX
            for (int k = i; k < j; ++k) {
                // 更新dp[i][j]为合并成一堆的最小花费
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + prefixSum[j + 1] - prefixSum[i]);
            }
        }
    }
    
    // 返回合并整个区间的最小花费
    return dp[0][n - 1];
}

int main() {
    vector<int> stones = {1, 2, 3, 4, 5}; // 示例石子数组
    cout << "Minimum cost to merge all stones: " << mergeStones(stones) << endl;
    return 0;
}
Scroll to Top