小编uty*_*yle的帖子

比方说,我们有一个列表/正整数数组x1,x2,...,xn.我们可以对这个序列进行连接操作,这意味着我们可以用一个元素替换两个彼此相邻的元素,这是这些元素的总和.例如:

- > array/list:[1; 2; 3; 4; 5; 6]

• 我们可以加入 2和3,并用5替换它们;
• 我们可以加入 5和6,并用11替换它们;
• 我们不能 加入 2和4;
• 我们不能 加入 1和3等

主要问题是找到给定序列的最小连接操作,之后该序列将按递增顺序排序.

注:空和一个元素序列都在增加顺序排序.

基本示例:

• 对于[4; 6; 5; 3; 9]解决方案是1(我们加入 5和3)

• 对于[1; 3; 6; 5]解决方案也是1(我们加入 6和5)

我正在寻找的是一种解决这个问题的算法.它可以是伪代码,C,C++,PHP,OCaml或类似的(我的意思是:如果你用其中一种语言编写解决方案,我会理解解决方案).