讨论/题目交流/求差价最优值/
求差价最优值

给定一个price数组,表示商品每天的价格,商人可以在i天买入该商品放入库房,j天卖出,所得利润为价格差减去保管费,费用每天1元,即j-i,j>=i,求最优收益。

这道题第一思路是用动态规划,奈何一直写不出最优解,大家有啥好招吗?

动态规划中关于数组求最优解的情况,我个人觉得一般两个方向:一,F(i)存储之前已经计算过的值,二,F(i)表示下标<=i情况下的最优解。
这道题你可以按情况2理解,F(i)=max(price[j]-price[k],F(i-1))-(j-k-1),且i>=j>=k。
你可以在草稿纸上画一个dp数组,然后按照计算F(i)的方法往里面填数据,找几个例子测一下如果ok就写成代码再测一下

展开全部 4 讨论