C++前缀和算法:合并石头的最低成本原理、源码及测试用例(一)

简介: C++前缀和算法:合并石头的最低成本原理、源码及测试用例

本文涉及的基础知识点

C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

动态规划,日后完成。

题目

有 n 堆石头排成一排,第 i 堆中有 stones[i] 块石头。

每次 移动 需要将 连续的 k 堆石头合并为一堆,而这次移动的成本为这 k 堆中石头的总数。

返回把所有石头合并成一堆的最低成本。如果无法合并成一堆,返回 -1 。

示例 1:

输入:stones = [3,2,4,1], K = 2

输出:20

解释:

从 [3, 2, 4, 1] 开始。

合并 [3, 2],成本为 5,剩下 [5, 4, 1]。

合并 [4, 1],成本为 5,剩下 [5, 5]。

合并 [5, 5],成本为 10,剩下 [10]。

总成本 20,这是可能的最小值。

示例 2:

输入:stones = [3,2,4,1], K = 3

输出:-1

解释:任何合并操作后,都会剩下 2 堆,我们无法再进行合并。所以这项任务是不可能完成的。.

示例 3:

输入:stones = [3,5,1,2,6], K = 3

输出:25

解释:

从 [3, 5, 1, 2, 6] 开始。

合并 [5, 1, 2],成本为 8,剩下 [3, 8, 6]。

合并 [3, 8, 6],成本为 17,剩下 [17]。

总成本 25,这是可能的最小值。

提示:

n == stones.length

1 <= n <= 30

1 <= stones[i] <= 100

2 <= k <= 30

分析

dp[begin][end]记录stones[begin,end)合并后的最小得分。时间复杂度O(nnn),状态数:n*n,转移状态时间复杂度O(n)。

状态转移

假定stones[begin,end)是由stone[begin,m)和stone[m,end)合并成的,m取值范围(begin,end)。stone[begin,m)简称左堆,stone[m,end)简称右堆。

左右两堆剩余石头数之和小于k dp[begin][end] = dp[begin][m]+dp[m][end]
左右两堆剩余石头数之和等于于k dp[begin][end] = dp[begin][m]+dp[m][end]+vPreSum[begin][end],石头发生了合并
左右两堆剩余石头数之和大于于k 抛弃

左右两堆剩余石头数之和大于于k

抛弃左右两堆剩余石头数之和大于于k,也可以找到最优解。

最后一轮 只有k个石头,故不会超过k
倒数第二轮 只有2k-1个石头,假定其范围是[i0,j0),倒数第二轮是[i1,j1), 那么[i0,j0)会合并,这时两堆石头恰好是k,故不会超过k

剩余石头数

每次合并后,石头数减少k-1。所有石头数减1,再对k-1求求余,再加1。

注意:先判断石头数是否是1,不是直接返回-1。

代码

核心代码

class Solution {
public:
  int mergeStones(vector<int>& stones, int K) {
    m_c = stones.size();
    if (1 != RemainLen(m_c,K))
    {
      return -1;
    }
    vector<int> vPreSum = { 0 };
    for (const auto& n : stones)
    {
      vPreSum.emplace_back(n + vPreSum.back());
    }
    vector<vector<int>> dp(m_c,vector<int>(m_c+1));//dp[i][j] 表示合并stones[i,j)的最小成本
    for (int len = 2; len <= m_c; len++)
    {
      for (int begin = 0; begin + len <= m_c; begin++)
      {
        const int end = begin + len;
        int iMin = INT_MAX;
        for (int m = begin + 1; m < end; m++)
        {
          const int iAdd = RemainLen(m - begin, K) + RemainLen(end - m, K);
          if (iAdd > K)
          {
            continue;
          }
          int cur = dp[begin][m] + dp[m][end];
          iMin = min(iMin, cur);
        }
        if (1 == RemainLen(len, K))
        {
          iMin += vPreSum[end] - vPreSum[begin];
        }
        dp[begin][end] = iMin;
      }     
    }
    return dp.front().back();
  }
  int RemainLen(int len, int k)
  {
    return 1+(len - 1) % (k - 1);
  }
  int m_c;
};

测试代码

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    assert(v1[i] == v2[i]);
  }
}
template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
int main()
{
  vector<int> stones = { 3,5,1,2,6 };
  int k = 3;
  int res = Solution().mergeStones(stones, k);
  Assert(25, res);
  stones = { 3,2,4,1 };
   k = 2;
   res = Solution().mergeStones(stones, k);
  Assert(20, res); 
  stones = { 1,2,3,4,5,6,7 };
  k = 3;
  res = Solution().mergeStones(stones, k);
  Assert(49, res);
  stones = { 1,2,3,4,5,6,7 };
  k = 4;
  res = Solution().mergeStones(stones, k);
  Assert(38, res);
  stones = { 1,2,3,4,5,6,7,8,9 };
  k = 5;
  res = Solution().mergeStones(stones, k);
  Assert(60, res);
  //
  stones = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
  k = 2;
  res = Solution().mergeStones(stones, k);
  Assert(135, res);
  stones = { 9,8,7,6,5,4,3,2,1 };
  k = 3;
  res = Solution().mergeStones(stones, k);
  Assert(87, res);
  stones = { 10,9,8,7,6,5,4,3,2,1 };
  k = 4;
  res = Solution().mergeStones(stones, k);
  Assert(91, res);
  //
  stones = { 5,8,7,6,5,12,13,14,4,3,2,1,2 };
  k = 4;
  res = Solution().mergeStones(stones, k);
  Assert(155, res);
  stones = { 2,8,7,6,5,12,13,14,4,3,2,1,2 };
  k = 5;
  res = Solution().mergeStones(stones, k);
  Assert(119, res);
  //CConsole::Out(res);
}

相关文章
|
1月前
|
C++
【C++】深入解析C/C++内存管理:new与delete的使用及原理(二)
【C++】深入解析C/C++内存管理:new与delete的使用及原理
|
1月前
|
编译器 C++ 开发者
【C++】深入解析C/C++内存管理:new与delete的使用及原理(三)
【C++】深入解析C/C++内存管理:new与delete的使用及原理
|
1月前
|
存储 C语言 C++
【C++】深入解析C/C++内存管理:new与delete的使用及原理(一)
【C++】深入解析C/C++内存管理:new与delete的使用及原理
|
2天前
|
搜索推荐 算法 C语言
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
24 8
|
2天前
|
搜索推荐 算法 C语言
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
20 7
|
1月前
|
分布式计算 监控 Hadoop
Hadoop-29 ZooKeeper集群 Watcher机制 工作原理 与 ZK基本命令 测试集群效果 3台公网云服务器
Hadoop-29 ZooKeeper集群 Watcher机制 工作原理 与 ZK基本命令 测试集群效果 3台公网云服务器
37 1
|
1月前
|
C++
C++番外篇——虚拟继承解决数据冗余和二义性的原理
C++番外篇——虚拟继承解决数据冗余和二义性的原理
39 1
|
26天前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
20 0
|
1月前
|
存储 算法 程序员
迪杰斯特拉(Dijkstra)算法(C/C++)
迪杰斯特拉(Dijkstra)算法(C/C++)
|
1月前
|
人工智能 算法 Java
【搜索算法】数字游戏(C/C++)
【搜索算法】数字游戏(C/C++)

热门文章

最新文章