视频字幕
区间动态规划是一种解决与序列的连续子区间相关的优化问题的技术。这类问题的特点是，一个较大区间的解可以由其内部较小区间的解合并或组合得到。在区间动态规划中，我们通常定义状态dp[i][j]表示对序列中从索引i到j的子区间进行操作后的最优解。计算顺序是按照区间长度从小到大进行，这样可以确保在计算大区间的解时，所有需要的小区间的解都已经计算出来了。
区间动态规划的基本步骤包括四个关键部分。首先，我们定义状态dp[i][j]表示处理区间[i,j]的最优解。其次，确定边界条件，通常是处理长度为1的区间，即dp[i][i]的值。第三，确定状态转移方程，一般形式为dp[i][j]等于在i到j-1之间枚举分割点k，取dp[i][k]加dp[k+1][j]再加上合并这两个子区间的代价的最小值。最后，我们按照区间长度从小到大进行计算，确保在计算大区间时，所有需要的小区间的值都已经计算出来了。例如，计算dp[2][4]时，我们需要考虑分割点k=2和k=3两种情况，分别计算并取最小值。
石子合并是区间动态规划的经典问题。问题描述为：有N堆石子排成一排，每次只能合并相邻的两堆石子，合并的代价为两堆石子的总重量，求将所有石子合并成一堆的最小总代价。我们定义状态dp[i][j]表示将第i堆到第j堆石子合并成一堆的最小代价。状态转移方程为：dp[i][j]等于在i到j-1之间枚举分割点k，取dp[i][k]加dp[k+1][j]再加上区间[i,j]内所有石子的重量和的最小值。其中区间内石子的重量和可以用前缀和快速计算。例如，计算dp[1][3]时，我们需要考虑k=1和k=2两种情况，分别计算并取最小值15。这种合并方式对应的是先合并第1堆和第2堆石子，代价为5，然后再合并这个新堆与第3堆石子，代价为10，总代价为15。
接下来，我们看看如何用C++实现石子合并这个区间动态规划问题。实现的关键步骤包括：使用二维数组dp[n][n]存储状态，计算前缀和来优化区间和的查询，以及按照区间长度从小到大进行枚举。在代码中，我们首先读入石子的数量和每堆石子的重量，然后计算前缀和数组，这样可以在O(1)时间内得到任意区间的石子总重量。接着，我们初始化dp数组，将对角线元素dp[i][i]设为0，表示单个石子堆不需要合并。然后，我们使用三重循环实现动态规划的计算过程：外层循环枚举区间长度，中层循环枚举区间起点，内层循环枚举分割点。最终，dp[0][n-1]就是将所有石子合并成一堆的最小代价。这个算法的时间复杂度是O(n³)，空间复杂度是O(n²)。
总结一下，区间动态规划是一种解决与序列的连续子区间相关优化问题的技术。它的核心思想是枚举区间长度和分割点，将大问题分解为小问题。我们通常定义状态dp[i][j]表示区间[i,j]的最优解，并按照区间长度从小到大的顺序进行计算，确保在计算大区间时，所有依赖的小区间问题都已经解决。除了我们详细讨论的石子合并问题外，区间DP还有许多其他应用场景，如矩阵链乘法问题，即求解一系列矩阵相乘的最小计算量；最优三角剖分问题，即将多边形划分为三角形，使得边权和最小；以及括号匹配问题，即计算需要添加的最少括号数量使表达式合法。区间DP的时间复杂度通常为O(n³)，这是因为有三层嵌套循环：枚举区间长度、起始点和分割点。而空间复杂度通常为O(n²)，用于存储DP表。通过掌握区间DP的思想和技巧，我们可以解决许多复杂的优化问题。