【求助】DP动态规划的问题，切木头
在OJ上看到一道题，题目如下：
背景
人们需要把一跟很长的木头切成几段，有一家名为 Analog Cutting Machinery (ACM) 的公司正在经营这一业务。他们根据切割前木头的长度来收费，木头越长、收费越高，并且每切割一次就收一次费。
显而易见，在这里切割木头时，不同的切割顺序就会产生不同的价钱。譬如一跟 10 米长的木头，需要在 2、4、7 米处切开。如果顺序在这三个位置切割，需要的费用是 10 + 8 + 6 = 24，因为木头原始长度为 10 米，切掉两米剩 8 米，在四米处切掉剩 6 米。如果按照 4、2、7 的顺序来切割，花费就是 10 + 4 + 6 = 20。
任务
你的老板有很多木材要切割，现在他希望你能够帮他找到最便宜的切割方式。
输入
一次输入可能包含多组数据。每一组数据的第一行是木材的长度L (L<=1000)，如果为 0 则表示输入结束。每组数据的第二行是要切割的次数 N (N<=50)，第三行则是切割的位置Ci (0<Ci<L)。以上数据均为整数。
输出
针对每一组输入，输出切割这段木头的最小费用。
Input
100
3
20 50 75
10
4
4 5 7 8
0
Output
200
22
我现在的想法是将切割开的每一段长度按从小到大排，然后每两个选择最小的相加，得到一段新的，和总和相加（ans+=new），然后再排序（插入排序），重复上述操作，最后得到总和。但是这个算法对其他测试用例过不了，希望大神指点指点！！！谢了！！这里还声明下，希望大神们讲下算法和大致思路就可以了，不要贴代码！！我还处于学习阶段！！谢谢！！
[解决办法]
你切割开来的排序以后，选择最小的相加，最小的两个不一定是相邻的，也就是说不可能有一次切割能同时切出你那两个最小。
实际上这题还是dp，dp[i,j]表示切割i到j段之间所有小段的最优解。根据定义dp[i,i]=0，然后转移有dp[i,j]=min(dp[i,k]+dp[k+1,j]) + len[j]-len[i-1]，其中len是每段的位置，并且补充定义len[0]=0
