什么样的算法适用？

Question

TLDR:我正在有效地寻找一种算法，该算法可以为我提供所需的最小总消息量的组合，无论它们是“顺序的”和/或“分层的”，以获得最终结果。

===为一家酒店设想连续12个星期。

这几周每周都有100美元的价格。

旅馆经理决定改变所有这些星期的价格。

​

他的系统目前只允许他发送“价格变动”信息，“sequentially”是这样的：

1. 第一周至第二周= 120美元
2. 第3至第4周= 150美元
3. 第五周至第六周= 120美元
4. 第7至第9周= 200美元
5. 第10周=120美元
6. 第11周=250美元
7. 第12周=120美元

但是，在这种情况下，他理解以“分层”的方式发送消息会更有效，如下所示：

1. 第一周至第十二周= 120美元
2. 第3至第4周= 150美元
3. 第7至第9周= 200美元
4. 第11周=250美元

哪一种算法允许管理者总是计算最优的“分层”选项？？，这样他就可以系统地选择最有效的发送消息的方式，不管涉及多少个星期，并且要记住，某些星期不一定会改变价格。

--我正在有效地寻找一种算法，该算法可以为我提供所需的最小总消息量的组合，无论它们是“顺序的”和/或“分层的”，以便得到最终的结果。这样的算法存在吗？

Answer 1

这里有一个自上而下的Python回忆录递归，它应该在O(n^4)时间内解决这个问题(实际上稍微长一点，因为它也在跟踪要做的动作--但这可以优化)：

class Memoize:
    def __init__(self, fn):
        self.fn = fn
        self.memo = {}
    def __call__(self, *args):
        if not self.memo.has_key(args):
            self.memo[args] = self.fn(*args)
        return self.memo[args]

@Memoize
def best_messages(a,b,value=None):
    """Return moves needed to make range old[a:b] have the target values

If value is not None, it means the range has been set to the given value
"""
    if value is None:
        while a<b and new[a]==old[a]:
            a+=1
        while a<b and new[b-1]==old[b-1]:
            b-=1     
    else:
        # Skip values that are correct
        while a<b and new[a]==value:
            a+=1
        while a<b and new[b-1]==value:
            b-=1     
    if a==b:
        return [] # Nothing to change

    best = None
    for s in range(a,b):
        for e in range(s+1,b+1):
            target = new[s]
            if target==new[e-1]:
                moves = [ (s,e,target) ] + best_messages(s,e,target) + best_messages(a,s,value) + best_messages(e,b,value) 
                if best is None or len(moves)<len(best):
                    best = moves
    return best

old = [100,100,100,100,100,100,100,100,100,100,100,100]
new = [120,120,150,150,120,120,200,200,200,120,250,120]
for s,e,value in best_messages(0,len(old))  :
    print "Week {} to Week {} = {}".format(s+1,e,value)

基本原则是，只考虑将更新中的第一个和最后一个设置为最终目标值的更新，因为否则我们可以使更新更短，并且仍然采取相同的移动次数。

更新

我认为，如果更改，可以优化为在O(n^3)时间内工作：

for s in range(a,b):

至

s=a