视频字幕
区间动态规划是一种特殊的动态规划方法，主要用于解决与序列或数组上的连续子区间相关的问题。它的核心特点是：状态定义通常为dp[i][j]，表示区间[i,j]的结果；大区间问题分解为小区间子问题；并按区间长度从小到大计算。在图示中，我们可以看到不同的区间，如dp[1][2]表示从索引1到2的子区间，dp[3][5]表示从索引3到5的子区间，而dp[0][5]则表示整个序列。
区间动态规划的解题步骤包括五个关键步骤。首先，定义状态，通常使用dp[i][j]表示区间[i,j]的结果。其次，确定基本情况，通常是长度为1或2的区间。第三，确定状态转移方程，通常通过选择分割点k将大区间分解为小区间。第四，确定计算顺序，按区间长度从小到大计算，确保计算dp[i][j]时所需的子问题已经解决。最后，最终结果通常为dp[0][n-1]，表示整个序列的解。在图示中，我们可以看到动态规划表格的填充顺序：先填充对角线上的基本情况，然后按区间长度递增的顺序填充其他单元格，最终得到右上角的最终结果。
石子合并是区间动态规划的经典例题。问题描述：有N堆石子排成一排，每堆石子有一个重量。每次可以合并相邻的两堆石子，新堆的重量为两堆石子的重量之和，合并的代价为两堆石子的重量之和。求将所有石子合并为一堆的最小代价。解题思路是：首先，定义状态dp[i][j]表示将区间[i,j]内的石子合并为一堆的最小代价。然后，状态转移方程为dp[i][j] = min{dp[i][k] + dp[k+1][j] + sum[i][j]}，其中k∈[i,j-1]，sum[i][j]为区间[i,j]内石子总重量。在图示中，我们可以看到五堆石子的重量分别为30、20、40、10和30，以及动态规划表格的填充过程。例如，合并前三堆石子的一种方式是先合并前两堆（代价50），再与第三堆合并（代价90），总代价为140。
区间动态规划还有许多其他经典例题。矩阵链乘法问题是给定n个矩阵的维度，求矩阵链相乘的最小计算量。状态dp[i][j]表示计算从第i个到第j个矩阵相乘的最小乘法次数。例如，对于三个矩阵A₁(2×3)、A₂(3×4)和A₃(4×2)，不同的计算顺序会导致不同的计算量：((A₁×A₂)×A₃)需要40次乘法，而(A₁×(A₂×A₃))只需要36次乘法。最长回文子序列问题是给定一个字符串，求其最长回文子序列的长度。状态dp[i][j]表示子串s[i...j]中最长回文子序列的长度。例如，字符串'babcba'的最长回文子序列是'baba'，长度为4。戳气球问题是有n个气球，每个气球上标有一个数字，戳破第i个气球可获得nums[i-1]*nums[i]*nums[i+1]个硬币，求能获得的最大硬币数。状态dp[i][j]表示戳破区间(i,j)中所有气球能获得的最大硬币数。这些问题都可以通过区间动态规划高效解决。
总结一下，区间动态规划是解决区间问题的有效方法。它的核心特点是：状态定义通常为dp[i][j]，表示区间[i,j]的结果；状态转移通常通过枚举分割点k，将大区间问题分解为小区间子问题；计算顺序按区间长度从小到大进行，确保计算dp[i][j]时所需的子问题已经解决。区间动态规划的经典例题包括石子合并、矩阵链乘法、最长回文子序列、戳气球问题等。这类问题的共同特点是，问题的解可以通过组合子问题的最优解得到，而子问题之间存在重叠，使得动态规划比暴力递归更高效。掌握区间动态规划的思想和方法，对于解决许多复杂的算法问题非常有帮助。