Description

将一根木棒折成若干份，每折一次的代价是当前这段木棒的长度, 总代价是折这根木棒直到满足要求所需要的所有操作的代价。例如，将一根长度为10的木棒折成四段，长度分别为2, 2, 3, 3，如果先折成长度为2和8的两段，再将长度为8的折成长度为2和6的两段，最后将长度为6的折成长度为3的两段，这些操作的代价是10+8+6=24；如果先折成长度为4和6的两段，在分别将长度为4的折成长度为2的两段、长度为6的折成长度为3的两段，则这些操作的代价是10+4+6=20，比上一种方案更好一些。

该问题的输入是木棒的长度L和一些整数c1,…,cn, 要求将木棒折成长度为c1, …, cn的n段且操作代价最小，请设计动态规划算法解决该问题。

分析

利用动态规划解决问题，最重要的是找到子问题，从而说明最优子结构和子问题重叠性，进而利用递归式解决。

这一问题的一个显然子问题是当木棒被折过之后，子木棒折成长度\(d_1, d_2, ..., d_m\) 的操作代价最小，其中\(d_i \in \{c_i\}\)

那么原问题可以表示为两个子问题的和的形式：即\(cost(origin) = cost(child_1) + cost(child_2) + L\)

那么考虑子问题的数量，难点出现了：按照道理讲，每个子问题的\(d_i\) 可以有\(O(2^n)\) 种取法。每个\(c_i\)在\(d_i\)中可以取或者不取。

一种思路是缩小子问题的空间，即不包括所有的子问题，只需要包括的子问题一定可以组合成原问题的最优解。因为这一问题的子问题是如此的自然，我们当然不会去想换个子问题的表达形式。

进一步分析所求的问题。发现一个有趣的性质：

把可行解用二叉树表示：

总代价正好等于内部节点的值得和，用叶节点的关系表示可以写成：

\(cost(T) = \sum_{j=1}^n x_{ij}d_T(x_{ij})\)

其中\(x_{ij}表示叶节点的值，d_T(x_{ij})表示叶节点的深度\)

对于一棵固定形状的树，叶节点的深度是固定的。从而对于不同的叶节点的值，有排序不等式：

\(\sum_{j=1}^n x_{ij}d_T(x_{ij}) >= \sum_{j=1}^n x_{ij}^{'}d_T^{'}(x_{ij})\)

其中\(x_{ij}^{'}d_T^{'}(x_{ij})\)中一者为原序列正序，一者为原序列倒序

即最小的叶节点分配最大的深度，依次往复。是不是有点像哈夫曼树？可以证明，这个问题具有优化子结构和贪心选择性，从而可以用贪心法解决。

说了这么多，似乎对之前的问题没有帮助啊。其实不然，既然我们知道了最优解如何构造，那么我们就构造一组包含最优解的可行解就可以了。由之前的分析，对叶节点正序排序，再直接分隔划分，就可以得到包含最优解的一组解了。

解答

先将\(c_1, ..., c_n\) 升序排序，再进行dp。

设dp[i, j] 是 折为长度\(c_i, ..., c_j\)的最优解。

\(dp[i,j] = min\{dp[i,k] + dp[k+1, j] + c_i + ... + c_j\}\)

其中dp[i,i] = 0

\(dp[i, i+1] = c_i+c_{i+1}\)

时间复杂度\(O（n^3)\)