如何理解线性分区中的动态编程解决方案？

如何理解线性分区中的动态编程解决方案？

请注意，本书中对算法的解释有一个小错误，请在勘误表中查找文本“（*）Page
297”。

关于您的问题：

1. 不，项目不需要排序，仅是连续的（也就是说，您不能重新排列它们）
2. 我认为，可视化算法的最简单方法是通过手动跟踪

   reconstruct_partition

   过程，以图8.8中最右边的表为指导。
3. 在书中，它指出m [i] [j]是“在{s1，s2，…，si}的所有分区上的最小可能成本”到j个范围内，其中分区的成本是…的大和。元素。”换句话说，这是“总和的最小最大值”，如果您原谅术语滥用的话。另一方面，d [i] [j]存储用于定位的索引位置给定对i，j的分区，如之前定义
4. 有关“成本”的含义，请参见上一个答案

编辑：

这是线性划分算法的实现。它基于Skiena的算法，但是采用Python方式；并返回分区列表。

from operator import itemgetterdef 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)]] + ansdef 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)