UVA 10003 - Cutting Sticks

  题目链接：Click Here~

  题意分析：

     给一根长为L的木棒，然后给出要切的N处地方。要你用最少的花费完毕这项任务。

而花费是怎样计算的呢？就是用当前木棒的长度是多少。那么花费就是多少。

算法分析：

    运用记忆化的过程能够缩减非常多时间。本题的实质是区间DP。原题是经典的石子合并问题。假设。感觉不好理解能够想想图论中的Flody模型。

状态转移方程：dp[i][j] = min(dp[i][j],solve(i,k)+solve(k,j)+len[j]-len[i])本质就是flody的模型转换。

运用到记忆化搜索的时候，终止条件一般有两个，一个是依据题目的要求能够推出。还有一个当然是为了避免反复计算而直接运用曾经得出的结果。

本题的条件一是if(i+1 == j) return 0;即：合并的区间仅仅有自己一个。