我努力理解动态规划的解决方案，以线性划分问题。我读的算法设计手册的问题在第8.5节所述。我读过的部分无数次，但我只是没有得到它。我认为这是一个贫穷的解释（在我读过到现在已经好多了），但我没能理解这个问题不够好，找了另一种解释。链接到更好的解释欢迎！

I'm struggling to understand the dynamic programming solution to linear partitioning problem. I am reading the The Algorithm Design Manual and the problem is described in section 8.5. I've read the section countless times but I'm just not getting it. I think it's a poor explanation (the what I've read up to now has been much better), but I've not been able to understand the problem well enough to look for an alternative explanation. Links to better explanations welcome!

更新：我发现有类似文字的书（也许从本书的第一版）页：的errata 文本（*），页297。

Be aware that there's a small mistake in the explanation of the algorithm in the book, look in the errata for the text "(*) Page 297".

关于你的问题：

否，项目不需要进行排序，只有连续的（也就是说，你不能重新排列它们） 我相信，以可视化的算法，最简单的方法是用手工跟踪 reconstruct_partition 操作，使用最右边的表图8.8为指导 在书它指出米[Ⅰ] [j]的是最小的可能成本比的所有分区成为{S1，S2，...，SI}成J个范围，其中一个分区的成本是拉尔在其部分之一的元素的总和。换句话说，它是最小的最大的总和，如果你赦免术语的滥用。另一方面，D [I] [j]的存储这是索引位置用于制造为给定的一对I，J分区如前定义 对于成本的含义，见previous答案 No, the items don't need to be sorted, only contiguous (that is, you can't rearrange them) I believe the easiest way to visualize the algorithm is by tracing by hand the reconstruct_partition procedure, using the rightmost table in figure 8.8 as a guide In the book it states that m[i][j] is "the minimum possible cost over all partitionings of {s1, s2, ... , si}" into j ranges, where the cost of a partition is the larges sum of elements in one of its parts". In other words, it's the "smallest maximum of sums", if you pardon the abuse of terminology. On the other hand, d[i][j] stores the index position which was used to make a partition for a given pair i,j as defined before For the meaning of "cost", see the previous answer

编辑：

下面是我实现线性分割算法。它是基于Skiena的算法，但在Python的方式;和它返回分区列表

Here's my implementation of the linear partitioning algorithm. It's based on Skiena's algorithm, but in a pythonic way; and it returns a list of the partitions.

from operator import itemgetter

def linear_partition(seq, k):
    if k <= 0:
        return []
    n = len(seq) - 1
    if k > n:
        return map(lambda x: [x], seq)
    table, solution = linear_partition_table(seq, k)
    k, ans = k-2, []
    while k >= 0:
        ans = [[seq[i] for i in xrange(solution[n-1][k]+1, n+1)]] + ans
        n, k = solution[n-1][k], k-1
    return [[seq[i] for i in xrange(0, n+1)]] + ans

def linear_partition_table(seq, k):
    n = len(seq)
    table = [[0] * k for x in xrange(n)]
    solution = [[0] * (k-1) for x in xrange(n-1)]
    for i in xrange(n):
        table[i][0] = seq[i] + (table[i-1][0] if i else 0)
    for j in xrange(k):
        table[0][j] = seq[0]
    for i in xrange(1, n):
        for j in xrange(1, k):
            table[i][j], solution[i-1][j-1] = min(
                ((max(table[x][j-1], table[i][0]-table[x][0]), x) for x in xrange(i)),
                key=itemgetter(0))
    return (table, solution)