You need to enable JavaScript to run this app. 不改变数组元素相对顺序的连续非空分区方案总数求解
优惠活动
大模型
产品
解决方案
定价
更多

不改变数组元素相对顺序的连续非空分区方案总数求解

连续非空子数组分区方案数计算

问题说明

给定长度为n的整数数组(数组元素无需互不相同),计算在不改变数组元素相对顺序的前提下,将数组划分为若干个连续非空子数组的总方案数。

分区规则示例

以数组 A = [1,2,3] 作为参考:

合法分区(共4种)

  • 整段不拆分:{1,2,3}
  • 第1、2个元素间隙拆分:{1} {2,3}
  • 第2、3个元素间隙拆分:{1,2} {3}
  • 两个间隙全部拆分:{1} {2} {3}

非法分区示例

{1,3} {2} 属于不合法的分区形式,这类划分打破了原数组的连续相对顺序,没有按照连续段的规则切割数组。

方案数计算逻辑

长度为n的数组,相邻元素之间一共存在n-1个可独立决策的拆分间隙,每个间隙有两种可选操作:插入分隔符拆分为两个子段、不插入分隔符保持相邻元素同属一个子段。
所有独立决策的组合总数即为最终方案数,对应计算规则为:

总方案数 = 2的(n-1)次方,代码实现可写为 total = 2 ** (n - 1)
以n=3的数组为例,代入公式得到2(3-1)=4,和前面枚举的合法分区数完全匹配;当n=1时,不存在可拆分的间隙,代入公式得到2(1-1)=1,对应单元素数组只有整段保留的1种方案,符合实际场景。


内容的提问来源于stack exchange,提问作者BeruboIV

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.07 19:36:04