擅长:python、mysql、java
<p>这是一个动态规划问题</p>
<p>首先建立以下数据结构</p>
<pre><code>for each position in the array
for each count of how many splits
(current max, sum of maxes, position of last split)
</code></pre>
<p>例如,在您的问题中,数据结构如下所示:</p>
<pre><code>[ # One group, no splits
[(10, 10, 0)], # 2 groups, 1 split
[(30, 30, 0), (30, 40, 1)],
[(40, 40, 0), (40, 50, 1), (40, 80, 2)],
[(40, 40, 0), (20, 50, 1), (20, 70, 3)],
[(50, 50, 0), (50, 60, 1), (50, 100, 2)], # the choices are equal
]
</code></pre>
<p>这可以通过简单的双循环创建。你从<code>[[(a[0], a[0], 0)]]</code>开始。要计算<code>i, j</code>项,您必须查看在<code>(i-1, j-1)</code>项之后启动一个新组,或者将当前元素添加到<code>(i-1, j)</code>项中的最后一个组</p>
<p>完成此操作后,从阵列的最后一个位置和所需的分割数开始。数据结构告诉您上一次拆分的位置,然后您转到该位置并向下拆分一次,以找到前一次拆分的位置。沿着饼干屑的痕迹往回走,你会发现所有的裂口</p>
<p>在您的示例中,<code>(len(a), x)</code>条目位于<code>(4, 1)</code>,并且具有值<code>(50, 60, 1)</code>。上一个条目位于<code>(1, 0)</code>,其值为<code>(10, 10, 0)</code>。我们忽略边界处的分裂,得到<code>[1]</code>作为答案</p>
<p>如果你想做<code>x=3</code>,那么你应该从<code>(50, 100, 2)</code>开始,回到<code>(40, 50, 1)</code>,然后到<code>(10, 10, 0)</code>,得到<code>[1, 2]</code>的答案</p>