Google

yangzeyao · 2015-11-12 06:59:01

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

1. 三种水果，价钱分别是x,y,z给你m的钱，一定要把钱花到不能买水果的情况下，最少买多少水果一开始说贪心算法，先从最贵的买起，然后他说most case work，让我想反例。

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

也只是用两个array优化了插入的时间复杂度,并没有优化空间复杂度。

哎，感觉不是很好，希望能给个二面机会。

宝贝忆彼岸 · 2015-11-12 07:45:31

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

Mr.Sagemaker · 2015-11-12 07:07:21

多谢分享！第一题：类似min coin change，greedy并不能保证对所有价钱组合都给最优，但是DP可以。转换方程基本不变，除了终止条件由0变到小于最小的物品单价。第二题LC原题变形，ugly num

yangzeyao · 2015-11-12 07:22:58

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

hyliu0000 · 2015-11-12 08:05:59

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

Mr.Sagemaker · 2015-11-12 08:45:56

hyliu0000 发表于 2015-11-12 08:05
第一题我感觉可以
dp[j] = Max(dp[j]) + prices[j] i 是第几个水果， j是那种水果，

复制代码

hyliu0000 · 2015-11-12 08:52:11

marthew777 发表于 2015-11-12 08:45

比我的要好，谢谢

luzcn · 2015-11-12 08:54:28

marthew777 发表于 2015-11-12 07:07
多谢分享！第一题：类似min coin change，greedy并不能保证对所有价钱组合都给最优，但是DP可以。转换方程 ...

第一题他提示你Greedy不能保证正确的时候就应该想到DP了。第二题就是Ugly Number的简化版。

yjfox · 2015-11-12 12:49:58

第一题背包变种，dp无疑
第二题用heap 是要付出额外时间复杂度的，用lz自己想到的这个方法是线性时间
没错， ugly number

marvin_2015 · 2015-11-12 14:21:41

yjfox 发表于 2015-11-12 12:49
第一题背包变种，dp无疑
第二题用heap 是要付出额外时间复杂度的，用lz自己想到的这个方法是线性时间
没 ...

请教下能具体讲下第二题如何用ugly number的思路来解吗？i和j不像ugly number里的系数一样单调递增的。谢谢