好的，我们来看一个 区间动态规划 的经典题目： 环形数组上的最大连续子数组和问题（进阶版：允许取反一次） 题目描述 给定一个长度为 n 的环形整数数组 nums （即 nums[0] 和 nums[n-1] 相邻），允许你选择数组中的一段连续子数组，并将这段子数组的所有元素取反（只能取反一次，也可以不取反），然后求环形数组中的最大可能子数组和。 例如： 输入： nums = [1, -2, 3, -2] 输出： 7 解释：取子数组 [ -2 ] 取反变成 [2] ，则数组变为 [1, 2, 3, -2] ，环形最大子数组和是 1+2+3 = 6 ？不对，等一下，我们仔细分析。 实际上，取反 [ -2 ] 后数组是 [1, 2, 3, -2] ，最大子数组是 [1, 2, 3] 和为 6，但环形？环形最大子数组和要考虑跨越边界的连续段。 但这里我们换一个例子更清楚： 输入： nums = [5, -3, 5] 输出： 10 解释：取反 [-3] 得到 [5, 3, 5] ，环形最大子数组和是整个数组 5+3+5=13 ？等等，不对，题目是环形数组，但取反后求最大连续子数组和（环形），其实相当于两种情况： 最大连续子数组在中间（不跨越首尾） 最大连续子数组跨越首尾（即总和减去中间的最小连续子数组） 但允许取反一次，意味着我们可以选择一段连续子数组取反，相当于总和的变化是 原总和 + 2 * 取反段的和 （因为取反段的和从 S 变成 -S ，变化了 -2S ，所以总和变化是 -2S 吗？仔细想：原总和 total ，取反段和 sum_seg ，新总和 = total - sum_seg + (-sum_seg) = total - 2 * sum_seg 。但我们想让新总和的环形最大子数组和最大。 环形最大子数组和 = max(最大子数组和, total - 最小子数组和) （在非环形时，最大子数组和是 maxS ，最小子数组和是 minS ，环形最大和是 max(maxS, total - minS) ，当 minS 为负时 total - minS 可能更大）。 现在允许取反一段连续子数组，相当于我们可以选择一段 [i, j] 取反，然后计算新数组的环形最大子数组和。 问题转化 设原数组总和为 total 。 取反段的和为 sum_seg ，则新数组总和为 total - 2 * sum_seg 。 新数组的环形最大子数组和有两种情况： 不跨越首尾的最大子数组和（新数组的 maxS_new ） 跨越首尾的最大子数组和 = total_new - minS_new （其中 minS_new 是新数组的最小子数组和） 所以新数组的环形最大子数组和 = max(maxS_new, total_new - minS_new) 。 但 maxS_new 和 minS_new 都依赖于取反段的位置。 关键观察 取反一段连续子数组等价于： 原数组的取反段 [i, j] 在新数组里变成 -nums[i..j] 。 我们可以把问题看作：在原数组上，允许将一段连续子数组取反，然后求最大连续子数组和（可以环形）。 一个经典技巧： 最大子数组和允许取反一次 的问题可以转化为： 原数组的最大子数组和 与 原数组的最大子数组和（允许取反一段） 比较。 允许取反一段的最大子数组和 = max( maxSubarraySum(nums), total - minSubarraySum(nums) + 2 * maxPositiveAfterNegation ) 等等，这样很乱。 更清晰的思路： 定义 f(i) 为以 i 结尾的取反了一段子数组的最大和。 但这样是线性 DP，不是区间 DP。我们要用区间 DP 吗？ 其实这个问题的最优解法是： 最大环形子数组和允许取反一次 = max( 情况1：取反段与最大环形子数组不重叠时的最大和 情况2：取反段与最大环形子数组重叠时的最大和 ) 但这样复杂。我们换一个更经典的区间 DP 题目。 既然这个题目有点绕，我们换一个更标准的区间 DP 题目： 区间动态规划例题：切棍子的最小成本问题（带指定切割点顺序） 题目描述 给定一根长度为 n 单位的棍子，以及一个数组 cuts[] ，包含需要切割的位置（按位置坐标给出，在 [1, n-1] 范围内）。 每次切割的成本等于当前棍子的长度。 你可以任意调整切割的顺序，求最小的总切割成本。 例如： n = 7, cuts = [1, 3, 4, 5] 输出： 16 解题思路 问题分析 如果切割顺序任意，那么这是一个典型的区间 DP 问题。 我们考虑在棍子的区间 [left, right] 上，需要完成该区间内的所有切割，最小成本是多少。 状态定义 令 dp[i][j] 表示在棍子的一段（起点为 cuts[i-1] ，终点为 cuts[j+1] ）上，完成该段内部所有切割点（即 cuts[i] 到 cuts[j] ）的最小成本。 为了方便，我们在 cuts 数组前后加上 0 和 n ，并排序。 设 m = len(cuts) ，排序后 cuts 有 m+2 个元素： [0, ... , n] 。 我们实际区间是 (cuts[i-1], cuts[j+1]) 内部的切割点索引从 i 到 j 。 状态转移 对于区间 [i, j] ，如果 i > j ，则没有切割点，成本为 0。 否则，我们选择第一个切割点 k （ i <= k <= j ），切割成本为当前段长度 cuts[j+1] - cuts[i-1] 。 切割后分成左右两个区间 [i, k-1] 和 [k+1, j] ，递归计算左右区间的最小成本。 所以： 如果 i > j ， dp[i][j] = 0 。 计算顺序 按区间长度从小到大计算。 示例演算 n = 7, cuts = [1, 3, 4, 5] 排序后加边界： [0, 1, 3, 4, 5, 7] 索引：0:0, 1:1, 2:3, 3:4, 4:5, 5:7 我们考虑内部切割点索引 1~4（对应原 cuts）。 区间长度 L = j-i+1 从 1 开始： i=1, j=1 （切割点 {1}） 段长度 = cuts[ 2] - cuts[ 0 ] = 3 - 0 = 3 dp[1][1] = 0 + 0 + 3 = 3 i=2, j=2 （切割点 {3}） 段长度 = cuts[ 3] - cuts[ 1 ] = 4 - 1 = 3 dp[2][2] = 3 i=3, j=3 （切割点 {4}） 段长度 = cuts[ 4] - cuts[ 2 ] = 5 - 3 = 2 dp[3][3] = 2 i=4, j=4 （切割点 {5}） 段长度 = cuts[ 5] - cuts[ 3 ] = 7 - 4 = 3 dp[4][4] = 3 区间长度 L=2： i=1, j=2 （切割点 {1,3}） 段长度 = cuts[ 3] - cuts[ 0 ] = 4 - 0 = 4 选 k=1：成本 = dp[ 1][ 0] + dp[ 2][ 2 ] + 4 = 0 + 3 + 4 = 7 选 k=2：成本 = dp[ 1][ 1] + dp[ 3][ 2 ] + 4 = 3 + 0 + 4 = 7 min = 7 i=2, j=3 （切割点 {3,4}） 段长度 = cuts[ 4] - cuts[ 1 ] = 5 - 1 = 4 选 k=2：0 + dp[ 3][ 3 ] + 4 = 0 + 2 + 4 = 6 选 k=3：dp[ 2][ 2 ] + 0 + 4 = 3 + 0 + 4 = 7 min = 6 i=3, j=4 （切割点 {4,5}） 段长度 = cuts[ 5] - cuts[ 2 ] = 7 - 3 = 4 选 k=3：0 + dp[ 4][ 4 ] + 4 = 0 + 3 + 4 = 7 选 k=4：dp[ 3][ 3 ] + 0 + 4 = 2 + 0 + 4 = 6 min = 6 区间长度 L=3： i=1, j=3 （切割点 {1,3,4}） 段长度 = cuts[ 4] - cuts[ 0 ] = 5 - 0 = 5 选 k=1：0 + dp[ 2][ 3 ] + 5 = 0 + 6 + 5 = 11 选 k=2：dp[ 1][ 1] + dp[ 3][ 3 ] + 5 = 3 + 2 + 5 = 10 选 k=3：dp[ 1][ 2 ] + 0 + 5 = 7 + 0 + 5 = 12 min = 10 i=2, j=4 （切割点 {3,4,5}） 段长度 = cuts[ 5] - cuts[ 1 ] = 7 - 1 = 6 选 k=2：0 + dp[ 3][ 4 ] + 6 = 0 + 6 + 6 = 12 选 k=3：dp[ 2][ 2] + dp[ 4][ 4 ] + 6 = 3 + 3 + 6 = 12 选 k=4：dp[ 2][ 3 ] + 0 + 6 = 6 + 0 + 6 = 12 min = 12 区间长度 L=4： i=1, j=4 （切割点 {1,3,4,5}） 段长度 = cuts[ 5] - cuts[ 0 ] = 7 - 0 = 7 选 k=1：0 + dp[ 2][ 4 ] + 7 = 0 + 12 + 7 = 19 选 k=2：dp[ 1][ 1] + dp[ 3][ 4 ] + 7 = 3 + 6 + 7 = 16 选 k=3：dp[ 1][ 2] + dp[ 4][ 4 ] + 7 = 7 + 3 + 7 = 17 选 k=4：dp[ 1][ 3 ] + 0 + 7 = 10 + 0 + 7 = 17 min = 16 所以最小总成本 = 16。 这样我们就用区间 DP 解决了这个问题。