关注
复习下动态规划，首先呢，优化内存，用两个dp来存，并且倒序遍历
第一，分成不购买当前的dp0［i,j］表示在1-i个商品中选择，价格不超过j 的最大喜好值，以及dp1表示购买当前的，dp2表示半价购买当前的
第二，关于初始边界，都为0但是，当i为1的时候，无法半价购买，所以dp2仍然为0，当大于1的时候，就可以直接比较，
不购买当前商品，最大喜爱值为当前的钱💰购买0-i-1的商品的preDp0-1-2的最大值
原价购买，为当前的💰减去当前商品价格购买0-i-1的preDP的最大值+like i
然后半价购买
就是直接原价购买上一个商品的
第一，分成不购买当前的dp0［i,j］表示在1-i个商品中选择，价格不超过j 的最大喜好值，以及dp1表示购买当前的，dp2表示半价购买当前的
第二，关于初始边界，都为0但是，当i为1的时候，无法半价购买，所以dp2仍然为0，当大于1的时候，就可以直接比较，
不购买当前商品，最大喜爱值为当前的钱💰购买0-i-1的商品的preDp0-1-2的最大值
原价购买，为当前的💰减去当前商品价格购买0-i-1的preDP的最大值+like i
然后半价购买
就是直接原价购买上一个商品的
全部评论
貌似说什么得用long long，int会溢出
貌似不需要pre Dp直接倒序每次从后面开始更新即可
for i <- 1 ... n:
逆序
for j <- Money ... price：
不选当前dp0，以及原价买当前dp1，半价dp2
这里增加一个if如果i等于1，则只看前面的preDp0和1
maxPre1= max(preDp0 ... 2[i-1,j])
maxPrePrice = max(preDp0 ... 2[i-1, j-price ])
dp0[ i, j ] = maxPre1
dp1[i, j] = maxPrePrice + like[i]
再来一个半价购买当前的
这里增加一个if如果i等于1，则只看前面的preDp0和1
for j <- Money ... price/2:
dp2[i, j] = like[i] + dp1[i-1, j-price/2]
相关推荐
查看7道真题和解析 10-02 23:00
浙江工业大学 集成电路IC设计 点赞 评论 收藏
分享
鼠鼠能上岸吗：进行中是秋招大项目进行中，你还可以选别的岗位；已结束是这个岗位流程结束了；筛选中就是在简历筛选环节没hr捞
投递美团等公司10个岗位 点赞 评论 收藏
分享
09-06 12:49
门头沟学院 Java 
我也是，前两面还挺紧张认真的，全程大脑飞速运转
后面就越来越不想面了，不想说话不想思考 点赞 评论 收藏
分享
点赞 评论 收藏
分享