We have an array A with N elements. At any time, we can pick two adjacent elements of the array and replace them with their sum, thus getting a new array. We repeat the same operation as many times as we want. My question is, how many different arrays can we get, by aplying this operation any number of times?
我们有一个带有N个元素的数组A。在任何时候，我们可以选择数组的两个相邻元素并用它们的和替换它们，从而得到一个新的数组。我们要重复同样的操作。我的问题是，我们能得到多少个不同的数组?
1 个解决方案
#1
0
Are you sure that zeros and negatives are allowed? If only positive numbers are allowed, than result is simple :-)
你确定允许零和负数吗?如果只允许正数，那么结果很简单:-)
If list has n elements, than there are n-1 commas between pairs element pairs. Every new array is produced by changing some of commas with plus sing. With that we see there are 2^(n-1) different arrays.
如果列表中有n个元素，那么在对元素对之间就有n-1个逗号。每一个新的数组都是通过改变一些逗号加上sing来产生的。我们看到有2 ^(n - 1)不同的数组。
I think that with zeros it is possible to reduce problem to same sub-problem by working with left and right sub-arrays from zero(s). That is some recurrence, but I didn't figure it out yet :-/
我认为通过零操作可以将问题减少到相同的子问题，即从零(s)中处理左和右子数组。这是一个递归式，但我还没弄明白:-/。
With negative allowed it is much more complicated.
而负的允许则要复杂得多。
#1
0
Are you sure that zeros and negatives are allowed? If only positive numbers are allowed, than result is simple :-)
你确定允许零和负数吗?如果只允许正数，那么结果很简单:-)
If list has n elements, than there are n-1 commas between pairs element pairs. Every new array is produced by changing some of commas with plus sing. With that we see there are 2^(n-1) different arrays.
如果列表中有n个元素，那么在对元素对之间就有n-1个逗号。每一个新的数组都是通过改变一些逗号加上sing来产生的。我们看到有2 ^(n - 1)不同的数组。
I think that with zeros it is possible to reduce problem to same sub-problem by working with left and right sub-arrays from zero(s). That is some recurrence, but I didn't figure it out yet :-/
我认为通过零操作可以将问题减少到相同的子问题，即从零(s)中处理左和右子数组。这是一个递归式，但我还没弄明白:-/。
With negative allowed it is much more complicated.
而负的允许则要复杂得多。