切棍子的最小成本

一句话套路:在每个区间里枚举「第一刀先切哪一刀」,这一刀把整段劈成左右两个更小的子区间。下面按区间从短到长逐格填这张 dp 表。

先看表骨架:行列都对应排序后的端点 arr=[0, 1, 3, 4, 5, 7]。dp[i][j] 是「切开 arr[i] 到 arr[j] 之间所有切点」的最小成本。对角线、下方,以及相邻端点(j 比 i 大 1)这些格子里都没有内部切点,成本 0,已经直接填好;只有上三角里跨度更大的「·」还没算,我们从最短的区间开始填。

轮到 dp[0][2](紫格)。这段棍子从 0 到 3,长度 3。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 3;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。

试「第一刀先切 arr[1]=1」:它把整段劈成左段 dp[0][1]=0 和右段 dp[1][2]=0(两个蓝色依赖格),再加上这一刀的段长 3,候选总成本 3。

候选 3 刷新了最优,暂定 dp[0][2]=3,对应「第一刀先切 arr[1]=1」。

区间内所有候选 k 试完,dp[0][2]=3 锁定(变绿)。它代表把 0..3 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。

轮到 dp[1][3](紫格)。这段棍子从 1 到 4,长度 3。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 3;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。

试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[1][2]=0 和右段 dp[2][3]=0(两个蓝色依赖格),再加上这一刀的段长 3,候选总成本 3。

候选 3 刷新了最优,暂定 dp[1][3]=3,对应「第一刀先切 arr[2]=3」。

区间内所有候选 k 试完,dp[1][3]=3 锁定(变绿)。它代表把 1..4 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。

轮到 dp[2][4](紫格)。这段棍子从 3 到 5,长度 2。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 2;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。

试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[2][3]=0 和右段 dp[3][4]=0(两个蓝色依赖格),再加上这一刀的段长 2,候选总成本 2。

候选 2 刷新了最优,暂定 dp[2][4]=2,对应「第一刀先切 arr[3]=4」。

区间内所有候选 k 试完,dp[2][4]=2 锁定(变绿)。它代表把 3..5 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。

轮到 dp[3][5](紫格)。这段棍子从 4 到 7,长度 3。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 3;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。

试「第一刀先切 arr[4]=5」:它把整段劈成左段 dp[3][4]=0 和右段 dp[4][5]=0(两个蓝色依赖格),再加上这一刀的段长 3,候选总成本 3。

候选 3 刷新了最优,暂定 dp[3][5]=3,对应「第一刀先切 arr[4]=5」。

区间内所有候选 k 试完,dp[3][5]=3 锁定(变绿)。它代表把 4..7 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。

轮到 dp[0][3](紫格)。这段棍子从 0 到 4,长度 4。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 4;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。

试「第一刀先切 arr[1]=1」:它把整段劈成左段 dp[0][1]=0 和右段 dp[1][3]=3(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 7。

候选 7 刷新了最优,暂定 dp[0][3]=7,对应「第一刀先切 arr[1]=1」。

试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[0][2]=3 和右段 dp[2][3]=0(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 7。

候选 7 没有更小,但同样达到 7,属于并列最优;表里保留先记录的那个,结果不变。

区间内所有候选 k 试完,dp[0][3]=7 锁定(变绿)。它代表把 0..4 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。

轮到 dp[1][4](紫格)。这段棍子从 1 到 5,长度 4。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 4;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。

试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[1][2]=0 和右段 dp[2][4]=2(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 6。

候选 6 刷新了最优,暂定 dp[1][4]=6,对应「第一刀先切 arr[2]=3」。

试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[1][3]=3 和右段 dp[3][4]=0(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 7。

候选 7 没比当前最优 6 更省,这种劈法不划算,保留原最优。

区间内所有候选 k 试完,dp[1][4]=6 锁定(变绿)。它代表把 1..5 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。

轮到 dp[2][5](紫格)。这段棍子从 3 到 7,长度 4。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 4;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。

试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[2][3]=0 和右段 dp[3][5]=3(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 7。

候选 7 刷新了最优,暂定 dp[2][5]=7,对应「第一刀先切 arr[3]=4」。

试「第一刀先切 arr[4]=5」:它把整段劈成左段 dp[2][4]=2 和右段 dp[4][5]=0(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 6。

候选 6 刷新了最优,暂定 dp[2][5]=6,对应「第一刀先切 arr[4]=5」。

区间内所有候选 k 试完,dp[2][5]=6 锁定(变绿)。它代表把 3..7 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。

轮到 dp[0][4](紫格)。这段棍子从 0 到 5,长度 5。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 5;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。

试「第一刀先切 arr[1]=1」:它把整段劈成左段 dp[0][1]=0 和右段 dp[1][4]=6(两个蓝色依赖格),再加上这一刀的段长 5,候选总成本 11。

候选 11 刷新了最优,暂定 dp[0][4]=11,对应「第一刀先切 arr[1]=1」。

试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[0][2]=3 和右段 dp[2][4]=2(两个蓝色依赖格),再加上这一刀的段长 5,候选总成本 10。

候选 10 刷新了最优,暂定 dp[0][4]=10,对应「第一刀先切 arr[2]=3」。

试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[0][3]=7 和右段 dp[3][4]=0(两个蓝色依赖格),再加上这一刀的段长 5,候选总成本 12。

候选 12 没比当前最优 10 更省,这种劈法不划算,保留原最优。

区间内所有候选 k 试完,dp[0][4]=10 锁定(变绿)。它代表把 0..5 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。

轮到 dp[1][5](紫格)。这段棍子从 1 到 7,长度 6。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 6;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。

试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[1][2]=0 和右段 dp[2][5]=6(两个蓝色依赖格),再加上这一刀的段长 6,候选总成本 12。

候选 12 刷新了最优,暂定 dp[1][5]=12,对应「第一刀先切 arr[2]=3」。

试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[1][3]=3 和右段 dp[3][5]=3(两个蓝色依赖格),再加上这一刀的段长 6,候选总成本 12。

候选 12 没有更小,但同样达到 12,属于并列最优;表里保留先记录的那个,结果不变。

试「第一刀先切 arr[4]=5」:它把整段劈成左段 dp[1][4]=6 和右段 dp[4][5]=0(两个蓝色依赖格),再加上这一刀的段长 6,候选总成本 12。

候选 12 没有更小,但同样达到 12,属于并列最优;表里保留先记录的那个,结果不变。

区间内所有候选 k 试完,dp[1][5]=12 锁定(变绿)。它代表把 1..7 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。

轮到 dp[0][5](紫格)。这段棍子从 0 到 7,长度 7。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 7;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。

试「第一刀先切 arr[1]=1」:它把整段劈成左段 dp[0][1]=0 和右段 dp[1][5]=12(两个蓝色依赖格),再加上这一刀的段长 7,候选总成本 19。

候选 19 刷新了最优,暂定 dp[0][5]=19,对应「第一刀先切 arr[1]=1」。

试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[0][2]=3 和右段 dp[2][5]=6(两个蓝色依赖格),再加上这一刀的段长 7,候选总成本 16。

候选 16 刷新了最优,暂定 dp[0][5]=16,对应「第一刀先切 arr[2]=3」。

试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[0][3]=7 和右段 dp[3][5]=3(两个蓝色依赖格),再加上这一刀的段长 7,候选总成本 17。

候选 17 没比当前最优 16 更省,这种劈法不划算,保留原最优。

试「第一刀先切 arr[4]=5」:它把整段劈成左段 dp[0][4]=10 和右段 dp[4][5]=0(两个蓝色依赖格),再加上这一刀的段长 7,候选总成本 17。

候选 17 没比当前最优 16 更省,这种劈法不划算,保留原最优。

区间内所有候选 k 试完,dp[0][5]=16 锁定(变绿)。它代表把 0..7 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。

填到最右上角 dp[0][5]=16,它代表把整根棍子 0..7 的所有切点切开的最小总成本,就是最终答案 16。

只有一个切点时,成本恒等于整根长度;切点越多,切割顺序越关键,才需要 DP。

两个高频追问:为何枚举第一刀就够,以及 DP 如何把「顺序」隐藏进区间递归。