在不改变数组元素的相对顺序的情况下，数组的分区数是多少？

Question

我们得到了一个包含 n 个整数（不一定不同）的数组。将数组划分为连续的非空子数组的方法总数是多少？

示例：数组 A = [1,2,3]。那么分区数就是4:

{1,2,3}

{1} {2,3}

{1,2} {3}

{1} {2} {3}

错误的分区：{1,3} {2}

Answer 1

我先解释给定的数组A = [1,2,3]，然后扩展到长度为N的数组。

让我们将数组的元素表示为 3 个 distinct 个王国。数组的元素是否不同并不重要，我们必须假设它们是不同的。此外，假设任意 2 个相邻王国之间存在 Binary Switch。如果开关是 1，则在两个相邻王国之间创建分区 否则没有分区。

1 [0] 2 [0] 3 --> {1,2,3}

1 [1] 2 [0] 3 --> {1} {2,3}

1 [0] 2 [1] 3 --> {1,2} {3}

1 [1] 2 [1] 3 --> {1} {2} {3}

所以我们看到每个开关都有2种可能性[0]和[1]。这些开关的不同组合导致不同的分区。因此分区总数为 2 x 2 = 4.

扩展为N个元素，将有(N - 1)个开关，每个开关有2种可能性，分区总数为2 x 2 x 2 x ... x 2 (N - 1) 次= 2^(N - 1).

What is the number of paritions of an array without changing the relative order of the elements of the array?