一道dp算法面试题

小弟碰到一个dp算法题目，请地里各位大佬提供一些思路，题目如下：
有n个物体准备从，某A点运送到B点。用W[n]表示每个物体的重量，每个物体的运费跟重量的关系是一个一元二次方程，V(w) = aw^2+bw+c。 每个物体到达B的顺序必须与原始顺序一只，比如：第j个物体，可以与j-1个物体同时或者晚到。现在要求如何安排物体的运送方式，才能够获得最低的花费。

也就是如何组合，比如输入w1, w2, w3, w4, w5。 你要求在V(w) = aw^2+bw+c这个关系下，如何组合才能够获得最小运费。
回答就加米～～

可以看成是一个划分问题：1 2 3 | 4 5 | 6 7 8。题目就是让求如何设置这些隔板使得sum{V(w)}最小，如果n比较小的话就直接O(N^2)dp就好了，dp[i]表示0...i-1全部运送过去后的最小花费。

danceonly 发表于 2017-10-10 09:04
可以看成是一个划分问题：1 2 3 | 4 5 | 6 7 8。题目就是让求如何设置这些隔板使得sum{V(w)}最小，如果n比 ...

请问可以说的稍微详细点吗？ 定义状态用的也是dp(i)表示前i个的最小花费，但是仔细一想不太对，因为没次新加进来一个物体，前面所有组合好的，都有可能被打乱，得重新划分间隔。

"每个物体的运费跟重量的关系是一个一元二次方程，V(w) = aw^2+bw+c。"这句话，我的理解是，运送是一批一批地运送，是吧？就是说，如果一次运送物体a(3) b(4) 需要花费V(3+4)的代价？ 如果理解没错的话，dp[i]在寻找最优的时候需要遍历前面所有的dp[j](0 < j < i)，然后转移方程就是dp[i] = max(dp[i], dp[j] + V(sum[j+1, ..., i]))。如果理解错的话，当我没说过。

danceonly 发表于 2017-10-10 09:12
"每个物体的运费跟重量的关系是一个一元二次方程，V(w) = aw^2+bw+c。"这句话，我的理解是，运送是一批一批 ...

你的理解是没错的，但是状态转移方程，不是你写的那样。因为你得考虑j+1 - i个物体不一定是放在一起的。 可能j+1 到k 放一起， k+1到i放一起。 所以直接把j+1到i的重量相加，不一定能够得到最小运费。

如果我没想错的话。

"因为你得考虑j+1 - i个物体不一定是放在一起的。 可能j+1 到k 放一起， k+1到i放一起。"仔细思考下，这种可能在dp[i] = min(dp[i], dp[k] + V(sum[k+1, ..., i]))的时候会被枚举掉，因为dp[k]包含了dp[j] + V(sum[j+1, ..., k])，或者说dp[k] <= dp[j] + V(sum[j+1, ..., k])。// 之前的max -> min

danceonly 发表于 2017-10-10 09:32
"因为你得考虑j+1 - i个物体不一定是放在一起的。 可能j+1 到k 放一起， k+1到i放一起。"仔细思考下，这种 ...

dp[i] = min(dp[i], dp[k] + V(sum[k+1, ..., i]))，大概想明白了，dp[i]你初始化成正无穷。