基于某些标准的安全数组分区
safe array partition based on some criteria
我正在尝试解决 this problem。问题可以概括为：
给定一个整数序列，找不到安全分区，其中安全分区定义为：
安全分区是对子序列 S1,S2,…,SK 的分区，这样对于每个有效的 i、min(Si)≤|Si|≤max(Si)——也就是说，对于该分区中的每个子序列，其长度大于或等于等于其最小元素并小于或等于其最大元素。
例如：
Input => 1 6 2 3 4 3 4
Output => 6 partitions
[1],[6,2,3,4,3,4]
[1,6,2],[3,4,3,4]
[1,6,2,3],[4,3,4]
[1],[6,2],[3,4,3,4]
[1],[6,2,3],[4,3,4]
[1,6],[2,3],[4,3,4]
我可能可以在互联网上的某个地方找到解决方案，其中包括代码，但我更感兴趣的是找到解决这个问题的方法，所以我在这里问我在观察中遗漏了哪些要点。
当我读到这个问题时，这些是我脑海中浮现的东西：
- 如果索引
i 处的元素安全地扩展序列
可能它也可能是新 sequence.so 的开始
每个元素 i 都有两个选择是否扩展
顺序与否。
所以我认为它可以在数学上表示为，
p(0..N)=1+P(i..N)+P(i+1..N),if A[i] is safe to extend current partition
p(0..N)=1+ p(i..N), if A[i] can't be used to extend
其中 P 是配分函数。
这个推理有效吗？我错过了什么吗？
[我很难在没有实际给出解决方案的情况下给出方向，因为一旦一个人朝着正确的方向思考，那么解决方案就会变得显而易见。我将尝试强调一些可能使人走上正轨的事实。]
显式枚举安全分区是有问题的，因为有 O(2n) 个安全分区。例如：
1,N,1,N,1,N ... [N elements]
对于这个序列，在任何长度 > 1 的子序列和子序列 [1] 匹配条件。这样一个长度为n=2k的序列的安全分区数是3k-1。为了证明这一点，请看下面的
基础 k = 1: f(1) = f(2) = 1
步长假设：f(2k) = 3k-1.
f(2k+1) =
f(2k+2) = (f(2k) + f(2k-1)) + (f(2k-2) + f(2k-3)) + ... + f(1) + 1
= 2*(f(2k) + f(2k-2) + .. + f(2)) + 1
= 2 * (3k-1 + 3k-2 + ... + 1) + 1
= 2 * (3k - 1) / 2 + 1
= 3k
由于枚举是不可能的，为了任何合理的性能，解决方案必须以某种方式计算而不迭代。由于 1,N,...,1,N 有 3k-1 的证明不必显式枚举所有序列，因此其原理可以推广到任何序列。
备注：
我以前解决过类似的问题，所以方向很明确。对于这个问题，我试图将我的想法分解成可管理的东西，并提出了关于复杂性的想法。我有一种非常强烈的感觉，即使在写下它并试图证明它之前，它也是指数级的。这来自经验和看到其他问题。复杂度函数感觉比斐波那契数列更糟糕，因为向序列中添加一个元素似乎是在添加至少两个较小尺寸的元素（类似于斐波那契数列）。由于 Fibbonacci 是指数的，因此 1,...,1 分区必须是指数的。从那里继续并用递推关系对其进行分析。
我找到解决方案的确切方式符合我的思维方式。每个人都有适合自己的不同思维方式，他们需要发展并找到它。
这就是我如何开始怀疑tge示例中安全序列的数量是3k-1:
我递归计算了f(2k)，基本条件f(1)=f(2)=1。然后是 3:
[1,N,1]
[1],[N,1]
[1,N],[1]
4 个：
[1,N,1,N]
[1],[N,1,N]
[1,N],[1,N]
意思是f(3)=f(4)=3。然后我递归地应用了
f(2k+2)=2*(f(2k) + f(2k-2) + .. + f(2)) + 1
导致 f(2)=1，f(4)=3，f(6)=9，f(8)=27。这可疑地看起来像 3k-1。然后我只需要用归纳法证明这一点。
我正在尝试解决 this problem。问题可以概括为： 给定一个整数序列，找不到安全分区，其中安全分区定义为：
安全分区是对子序列 S1,S2,…,SK 的分区，这样对于每个有效的 i、min(Si)≤|Si|≤max(Si)——也就是说，对于该分区中的每个子序列，其长度大于或等于等于其最小元素并小于或等于其最大元素。
例如：
Input => 1 6 2 3 4 3 4
Output => 6 partitions
[1],[6,2,3,4,3,4]
[1,6,2],[3,4,3,4]
[1,6,2,3],[4,3,4]
[1],[6,2],[3,4,3,4]
[1],[6,2,3],[4,3,4]
[1,6],[2,3],[4,3,4]
我可能可以在互联网上的某个地方找到解决方案，其中包括代码，但我更感兴趣的是找到解决这个问题的方法，所以我在这里问我在观察中遗漏了哪些要点。
当我读到这个问题时，这些是我脑海中浮现的东西：
- 如果索引
i处的元素安全地扩展序列 可能它也可能是新 sequence.so 的开始 每个元素i都有两个选择是否扩展 顺序与否。
所以我认为它可以在数学上表示为，
p(0..N)=1+P(i..N)+P(i+1..N),if A[i] is safe to extend current partition
p(0..N)=1+ p(i..N), if A[i] can't be used to extend
其中 P 是配分函数。
这个推理有效吗？我错过了什么吗？
[我很难在没有实际给出解决方案的情况下给出方向，因为一旦一个人朝着正确的方向思考，那么解决方案就会变得显而易见。我将尝试强调一些可能使人走上正轨的事实。]
显式枚举安全分区是有问题的，因为有 O(2n) 个安全分区。例如：
1,N,1,N,1,N ... [N elements]
对于这个序列，在任何长度 > 1 的子序列和子序列 [1] 匹配条件。这样一个长度为n=2k的序列的安全分区数是3k-1。为了证明这一点，请看下面的
基础 k = 1: f(1) = f(2) = 1
步长假设：f(2k) = 3k-1.
f(2k+1) =
f(2k+2) = (f(2k) + f(2k-1)) + (f(2k-2) + f(2k-3)) + ... + f(1) + 1
= 2*(f(2k) + f(2k-2) + .. + f(2)) + 1
= 2 * (3k-1 + 3k-2 + ... + 1) + 1
= 2 * (3k - 1) / 2 + 1
= 3k
由于枚举是不可能的，为了任何合理的性能，解决方案必须以某种方式计算而不迭代。由于 1,N,...,1,N 有 3k-1 的证明不必显式枚举所有序列，因此其原理可以推广到任何序列。
备注：
我以前解决过类似的问题，所以方向很明确。对于这个问题，我试图将我的想法分解成可管理的东西，并提出了关于复杂性的想法。我有一种非常强烈的感觉，即使在写下它并试图证明它之前，它也是指数级的。这来自经验和看到其他问题。复杂度函数感觉比斐波那契数列更糟糕，因为向序列中添加一个元素似乎是在添加至少两个较小尺寸的元素（类似于斐波那契数列）。由于 Fibbonacci 是指数的，因此 1,...,1 分区必须是指数的。从那里继续并用递推关系对其进行分析。
我找到解决方案的确切方式符合我的思维方式。每个人都有适合自己的不同思维方式，他们需要发展并找到它。
这就是我如何开始怀疑tge示例中安全序列的数量是3k-1:
我递归计算了f(2k)，基本条件f(1)=f(2)=1。然后是 3:
[1,N,1]
[1],[N,1]
[1,N],[1]
4 个：
[1,N,1,N]
[1],[N,1,N]
[1,N],[1,N]
意思是f(3)=f(4)=3。然后我递归地应用了
f(2k+2)=2*(f(2k) + f(2k-2) + .. + f(2)) + 1
导致 f(2)=1，f(4)=3，f(6)=9，f(8)=27。这可疑地看起来像 3k-1。然后我只需要用归纳法证明这一点。